「CEOI2024」洒水器 题解

题目大意

有$N$个洒水器和$M$朵花，所有位置按非递减顺序给出。每个洒水器可以向左或向右旋转，喷水强度$K$相同。向左旋转覆盖区间$[s_i-K, s_i]$，向右旋转覆盖区间$[s_i, s_i+K]$。求最小的$K$使得所有花都被覆盖，并输出对应的洒水器方向配置。

算法思路

核心思想：二分答案 + 动态规划贪心

1. 二分答案：在$[0, 10^9]$范围内二分查找最小的喷水强度$K$
2. 动态规划验证：对于给定的$K$，使用动态规划判断是否存在可行的洒水器方向分配
3. 贪心构造：根据DP过程中记录的前驱信息还原洒水器方向

代码详解

数据结构定义

const int N = 1e5 + 5;
bool dir[N];      // dir[i]: 第i个洒水器的方向(0:左, 1:右)
int f[N], s[N];   // f[i]: DP数组，s[i]: 洒水器位置
int pre[N], p[N]; // pre[i]: 前驱指针，p[i]: 花的位置
int n, m;         // 洒水器数量，花的数量
char ans[N];      // 最终答案的方向字符串

关键函数：find(int x)

int find(int x) {
    return upper_bound(p + 1, p + 1 + m, x) - p - 1;
}

功能：在花的位置数组中找到最后一个位置$\leq x$的花的索引
数学意义：返回满足$p_i \leq x$的最大$i$

核心验证函数：check(int k)

bool check(int k) {
    f[0] = 0;  // 初始化：0个洒水器覆盖0朵花
    
    for (int i = 1; i <= n; ++i) {
        // 默认情况：第i个洒水器向右，继承前i-1个的状态
        f[i] = f[i - 1], pre[i] = i - 1, dir[i] = 1;
        
        // 情况1：如果前i-1个洒水器能覆盖到s[i]-1的位置
        // 那么第i个洒水器向右可以覆盖到s[i]+k
        if (f[i - 1] >= find(s[i] - 1))
            f[i] = find(s[i] + k);
        
        // 计算第i个洒水器向左旋转时需要的前置覆盖要求
        int pos = find(s[i] - k - 1);
        
        // 情况2：使用第i-1个洒水器向右，第i个洒水器向左
        if (i >= 2 && f[i - 2] >= pos) {
            int tmp = max(find(s[i - 1] + k), find(s[i]));
            if (tmp > f[i])
                f[i] = tmp, pre[i] = i - 2, dir[i] = 0;
        } 
        // 情况3：第i个洒水器单独向左
        else if (f[i - 1] >= pos) {
            int tmp = find(s[i]);
            if (tmp > f[i])
                f[i] = tmp, pre[i] = i - 1, dir[i] = 0;
        }
    }
    
    return f[n] == m;  // 检查是否覆盖了所有m朵花
}

DP状态定义：$f[i]$表示使用前$i$个洒水器最多能覆盖到前$f[i]$朵花

三种转移情况：

1. 洒水器i向右：如果前$i-1$个洒水器能覆盖到$s_i-1$，那么洒水器$i$向右可以覆盖到$s_i+K$
2. 洒水器i-1向右，洒水器i向左：需要前$i-2$个洒水器覆盖到$s_i-K-1$
3. 洒水器i单独向左：需要前$i-1$个洒水器覆盖到$s_i-K-1$

主函数：二分搜索与答案构造

int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n >> m;
    
    // 输入洒水器和花的位置（1-indexed）
    for (int i = 1; i <= n; ++i) cin >> s[i];
    for (int i = 1; i <= m; ++i) cin >> p[i];
    
    // 二分查找最小喷水强度K
    int l = 0, r = 1e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    
    // 输出结果
    if (check(l)) {
        cout << l << '\n';
        
        // 根据pre数组还原洒水器方向
        for (int i = n; i; i = pre[i]) {
            for (int j = pre[i] + 1; j < i; ++j)
                ans[j] = 'R';  // 中间未被特殊处理的洒水器默认向右
            ans[i] = (dir[i] ? 'R' : 'L');  // 根据dir设置方向
        }
        
        for (int i = 1; i <= n; ++i) cout << ans[i];
    } else {
        cout << -1;
    }
    
    return 0;
}

算法复杂度

• 时间复杂度：$O(N \log M \log K)$
  • 二分答案：$O(\log K)$，其中$K \leq 10^9$
  • 每次验证：$O(N \log M)$，find函数使用二分查找
• 空间复杂度：$O(N + M)$

关键点说明

1. 状态设计：$f[i]$表示覆盖的花数量而非位置，简化了状态转移
2. 贪心选择：总是尝试让当前洒水器覆盖尽可能多的花
3. 边界处理：通过find(s[i]-1)等调用正确处理区间边界
4. 方向记录：通过pre和dir数组记录决策路径，便于最终构造答案

该算法通过巧妙的动态规划设计，在二分答案的框架下高效解决了洒水器方向分配问题。