ROI2024 割草 题解

· · 题解

P11116 [ROI 2024] 割草 (Day 2) 题解

模拟赛 T1，场上想了二十分钟，有点困出去喝口水想出来了。

题意

给定 n 个机器人，每个机器人有三个属性：位置、能走的距离、初始方向，在起点和终点各有一个机器人，机器人按照位置从左向右依次给出。

所有机器人会同时开始向初始方向运行，中途不会改变方向，不能越过其他的机器人，也不能超过自己能够走到的距离。

我们有一种操作，每次可以修改一个机器人的初始方向。询问我们能否在一些次操作之后，使得所有区域都被覆盖，需要求出操作次数。

思考过程

看到部分分有很多，优先思考了部分分，在反复观察题面的时候发现了一个性质——面朝右侧运行的机器人是序列的一个前缀，而面向左侧的机器人是序列的一个后缀。

为什么呢？

题干里说到，机器人位置是严格递增的，也就是不会有重复。

想象一下，如果一个机器人面向左侧，它后面的机器人面向右侧，那么这两个机器人之间的部分就无法被覆盖到，因此得出了结论。

根据这条性质，我们可以找到面向右侧的机器人中，最靠后可以放在哪里，以及面向左侧的机器人中，最靠前可以放在哪里。

我们分别从前往后、从后往前各扫一遍，每次判断当前朝向能否覆盖到下一个位置（这里的当前朝向指的是前后缀的朝向，即前缀向右，后缀向左）。找到端点处两个位置，即最靠前/后的位置。如果这两个位置之间还存在机器人，那么这个机器人朝向左侧和右侧就都不合法了，因此无解，输出 -1。

判断完无解的情况，剩下的就是求出最小的操作次数。

不难发现，我们把面朝左侧这段后缀的左端点放在求出的两个位置之间都是合法的，因此我们只需要在这些方案里面取一个最小的即可。

我们直接枚举后缀的左端点所在的位置（第一个面朝左侧的机器人位置），随后把答案与每种方案的贡献比较并更新一下即可。

如何计算贡献，也就是如何快速数出这段前/后缀中有多少个方向不符的，我们使用前缀和维护出区间内操作之前初始状态面向右边的机器人数量，也可以快速求出一段区间内不合法的数量。

到这里就做完了，代码。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int pre[maxn];
int x[maxn],p[maxn],d[maxn];
signed main()
{
//  freopen("A1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> x[i] >> p[i] >> d[i];
    for(int i = 1;i <= n;i++) pre[i] = pre[i - 1] + (d[i] == 1);
    int ls = n,pr = 1;
    for(int i = 1;i < n;i++)
        if(x[i] + p[i] < x[i + 1])
        {
            ls = i;
            break;
        }

    if(x[ls + 1] - p[ls + 1] > x[ls] + p[ls]) ls--;
    for(int i = n;i > 1;i--)
        if(x[i] - p[i] > x[i - 1])
        {
            pr = i;
            break;
        }
    if(x[pr - 1] + p[pr - 1] < x[pr] - p[pr]) pr++;
    if(pr > ls + 1)
    {
        cout << -1 << endl;
        return 0;
    }
    int ans = 0x3f3f3f3f3f3f3f3f;
    for(int i = pr;i <= ls + 1;i++)//枚举  向左的部分的最左端的位置 
    {
        int sum = 0;
        int xy = i - 1;
        sum += xy - pre[xy];
        sum += pre[n] - pre[xy];
        ans = min(ans,sum);
    }
    cout << ans << endl;
    return 0;

}