洛谷P7745题解

#题解 2025-02-04

调了两个月终于调出来了。

首先看数据范围：且

纯根据题意模拟的肯定过不了

这时候就需要预处理。

如图，容易发现：

图上轴距离和为，轴距离和为。

, 轴距离和相加即为两个控制点到 ROBOT 的曼哈顿距离。

一提到预处理，首先我们想到的是前缀和。

求数组前缀和的方式十分简单，仅需要写一个循环，例如下方代码：

for(int i = 1; i < anumber; i++)
    xa[i] = xa[i - 1] + xa[i]; //计算前缀和核心代码，下同
for(int i = 1; i < anumber; i++)
    ya[i] = ya[i - 1] + ya[i];

在得到前缀和后，根据题意，容易得出每次移动对于每个控制点到ROBOT的距离或，我们只需要详细写出或即可。

同样的，这边放一个 gif 来演示收到 “J” 指令是的操作情况。

(如果 gif 挂了请@或私信我)

举例当指令为 “S” 时：

if(s[i] == 'S'){
    tot += yn[y + zs]; //需要+1的数
    tot -= (n - yn[y + zs]); //除去需要+1的，即为需要-1的
    y++; //对应题目
}

在一系列例如上方的处理后，我们仅需要提前(在输入每个机器人坐标时)算出初始距离，并对这个初始距离进行加减即可。

写完后发现时间复杂度仅有，可以轻松通过

当然，此题也可以用 STL 中的 lower_bound 和 upper_bound 写。