P10806 [CEOI 2024] 洒水器

· · 题解

前言

怎么题解区全是贪心的做法？来贡献一篇 dp 做法的题解。

"膜拜"同机房巨佬 @TTpandas 试图通过复杂度和正确性都错误的奇技淫巧通过此题。

题目大意

一个数轴上有 n 个洒水器和 m 个花盆，洒水器的强度为 k。

一个洒水器可以浇灌位于 [s_i-k,s_i] 或者 [s_i,s_i+k] 中的花朵，现在请你求出最小的 k，使得 m 朵话都至少被一个洒水器浇灌到，要求输出方案。

思路

首先一眼二分答案，考虑如何 check。

如果你做过 CF1476F，那么这道题就很简单了，因为你会发现这就是个经典的前缀覆盖问题。

令 dp_i 表示考虑完前 i 个洒水器，能够覆盖的最长花盆前缀。

令 lasR_i 表示最大的 j 满足 f_j < s_i，即洒水器往右旋转不能覆盖到的最靠左的花盆。

令 lasL_i 表示最大的 j 满足 f_j \le s_i \wedge f_j \ge s_i-k，即洒水器向左旋转可覆盖到的最靠右的花盆。

令 L_i 表示最大的 j 满足 f_j < s_i - k，即洒水器向左旋转仍无法覆盖到的最靠右的花盆。

令 R_i 表示最大的 j 满足 f_j \le s_i - k \wedge f_j \ge s_i，即洒水器向右旋转可覆盖到的最靠右的花盆。

显然这些值是很好求的，重点在于 dp 数组的转移。

有如下三种转移：

dp_i \leftarrow \max\{\max_{l < j < i}\{R_j\} , LasL_i\}

最后判断一下 dp_n \ge m 即可。

注意 dp 的时候记录一下转移路径，输出方案是容易的。

代码

时间复杂度 n\log^2n，但其实精细实现可做到 n\log n，不过没有这个必要，因为不卡常。

这里只给出 check 的核心代码。

bool check(int mid) {
    for (int i = 1 ; i <= n ; i ++) {
        int k = lower_bound(f + 1 , f + m + 1 , s[i] - mid) - f - 1;
        if (f[k] < s[i] - mid) L[i] = k;
        else L[i] = 0;
    }
    for (int i = 1 ; i <= n ; i ++) {
        int k = upper_bound(f + 1 , f + m + 1 , s[i] + mid) - f - 1;
        if (f[k] >= s[i] && f[k] <= s[i] + mid) R[i] = k;
        else R[i] = 0;
    }
    for (int i = 1 ; i <= n ; i ++) {
        int k = upper_bound(f + 1 , f + m + 1 , s[i]) - f - 1;
        if (f[k] >= s[i] - mid && f[k] <= s[i]) lasL[i] = k;
        else lasL[i] = 0;
        lasR[i] = lower_bound(f + 1 , f + m + 1 , s[i]) - f - 1;
    }
    for (int i = 1 ; i <= n ; i ++) Max[i][0] = R[i];
    for (int j = 1 ; j <= 17 ; j ++) {
        for (int i = 1 ; i + (1 << j) - 1 <= n ; i ++) {
            Max[i][j] = max(Max[i][j - 1] , Max[i + (1 << j - 1)][j - 1]);
        }
    }
    for (int i = 1 ; i <= n ; i ++) {
        dp[i] = dp[i - 1] , pre[i] = i - 1 , dir[i] = -1;
        if (dp[i - 1] >= lasR[i]) {
            if  (max(R[i] , lasL[i]) > dp[i]) {
                dp[i] = max(R[i] , lasL[i]) , dir[i] = 1 , pre[i] = i - 1;
            }
        }
        int l = 0 , r = i - 1;
        while(l < r) {
            int mid = l + r >> 1;
            if (dp[mid] >= L[i]) r = mid;
            else l = mid + 1;
        }
        if (dp[l] >= L[i]) {
            if (max(GetMax(l + 1 , i - 1) , lasL[i]) > dp[i]) {
                dp[i] = max(GetMax(l + 1 , i - 1) , lasL[i]);
                pre[i] = l , dir[i] = -1;
            }
        }
    }
    return (dp[n] >= m);
}