题解：割草机的崛起

题目分析

我们需要安排割草机器人的移动方向，使得整个草坪被完全修剪。草坪可以看作数轴上从 $x_1 = 0$ 到 $x_n$ 的区间，每个机器人有初始位置 $x_i$、最大移动距离 $p_i$ 和初始方向 $d_i$。

机器人会在以下情况停止：

1. 移动了最大距离 $p_i$
2. 到达草坪边界 ($x_1$ 或 $x_n$)
3. 与迎面而来或已停止的机器人相遇

关键思路

我们可以将问题分解为三个部分：

1. 从左到右检查连续性

定义 l[i] 表示前 $i$ 个机器人能否连续覆盖从 $x_1$ 到 $x_i$ 的区域：

• l[0] = true（空区间总是可覆盖）
• 对于 i ≥ 1，l[i] = l[i-1] && (x[i] - x[i-1] ≤ p[i-1]) 即：前 $i-1$ 个机器人能覆盖到 $x_{i-1}$，且第 $i-1$ 个机器人能到达 $x_i$

2. 从右到左检查连续性

定义 r[i] 表示从第 $i$ 个机器人到最后一个机器人能否连续覆盖从 $x_i$ 到 $x_n$ 的区域：

• r[n+1] = true
• 对于 i ≤ n，r[i] = r[i+1] && (x[i+1] - x[i] ≤ p[i+1])

3. 统计方向改变次数

我们维护两个前缀和数组：

• sum1[i]：前 $i$ 个机器人中初始方向向左的数量
• sum2[i]：从第 $i$ 个到最后一个机器人中初始方向向右的数量

解决方案

我们考虑三种情况：

1. 全部从左到右覆盖：如果 l[n] = true，则只需要改变所有向左的机器人方向，次数为 sum1[n]

2. 全部从右到左覆盖：如果 r[1] = true，则只需要改变所有向右的机器人方向，次数为 sum2[1]

3. 分割点覆盖：在位置 $i$ 分割，前 $i$ 个机器人向左覆盖，后 $n-i$ 个机器人向右覆盖。需要满足：

   • 前 $i$ 个能连续覆盖：l[i] = true
   • 后 $n-i$ 个能连续覆盖：r[i+1] = true
   • 中间空隙能被覆盖：x[i+1] - x[i] ≤ p[i] + p[i+1]
   • 改变次数：sum1[i] + sum2[i+1]

代码实现详解

#include <bits/stdc++.h>
#define INF 1e18
using namespace std;
const int N = 100009;
typedef long long ll;
ll n, ans = INF;
ll x[N], p[N], d[N];
ll sum1[N], sum2[N];  // 前缀和数组
bool l[N], r[N];      // 连续性标记

int main() {
    cin >> n;
    
    // 输入数据
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> p[i] >> d[i];
    
    // 从左到右检查连续性
    l[0] = 1;  // 空区间总是可覆盖
    for (int i = 1; i <= n; i++) {
        sum1[i] = sum1[i - 1] + (d[i] == -1);  // 统计向左的机器人
        l[i] = l[i - 1];  // 继承前i-1个的连续性
        
        // 检查第i-1个机器人能否到达第i个位置
        if (x[i] - x[i - 1] > p[i - 1])
            l[i] = 0;  // 无法连续覆盖
    }
    
    // 从右到左检查连续性
    r[n + 1] = 1;  // 空区间总是可覆盖
    for (int i = n; i >= 1; i--) {
        sum2[i] = sum2[i + 1] + (d[i] == 1);  // 统计向右的机器人
        r[i] = r[i + 1];  // 继承后i+1个的连续性
        
        // 检查第i+1个机器人能否到达第i个位置
        if (x[i + 1] - x[i] > p[i + 1])
            r[i] = 0;  // 无法连续覆盖
    }
    
    // 情况1：全部从左到右覆盖
    if (l[n])
        ans = min(ans, sum1[n]);
    
    // 情况2：全部从右到左覆盖
    if (r[1])
        ans = min(ans, sum2[1]);
    
    // 情况3：在位置i分割覆盖
    for (int i = 0; i <= n; i++)
        if (l[i] && r[i + 1] && x[i + 1] - x[i] <= p[i + 1] + p[i])
            ans = min(ans, sum1[i] + sum2[i + 1]);
    
    // 输出结果
    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
    
    return 0;
}

复杂度分析

• 时间复杂度：$O(n)$，我们只进行了三次线性遍历
• 空间复杂度：$O(n)$，用于存储前缀和数组和连续性标记

总结

本题通过前缀和与连续性检查，将复杂的最优化问题转化为线性可解的问题。关键在于发现草坪覆盖的连续性性质，以及合理分割覆盖区域的方法。