题解：P9292 [ROI 2018] Robomarathon

ALANYQ · 2025-10-02 16:40:23 · 题解

P9292 [ROI 2018] Robomarathon 题解

p=1：

明显对于 i 点，在第 i 点发唯一一个信号最优。
由于大小关系不变，我们可以衍生出两个数组 s1 跟 s2，s1_i=a_i-i，s2_i=a_i+i，则 ans_i 就会等于 1 到 i-1 中满足 s1_i > s1_j 的 j 的个数加上 i+1 到 n 中满足 s2_i > s2_j 的 j 的个数。
离散化与树状数组即可。时间复杂度 O(nlogn)。

p=2：

如果只有一个信号，则放在两端 1 或 n 最优。
如果有两个信号，可以证明放在 i-\min(i-1,n-i) 和 i+\min(i-1,n-i) 最优。在两个信号外的位置全部放上信号。
依旧离散化与树状数组。时间复杂度 O(nlogn)。