[CEOI2024] 洒水器

佬头 · 2024-07-27 12:41:30 · 题解

Description

现有 N 个洒水器和 M 朵花排成一排，洒水器位于 s_1,s_2,\ldots,s_N~(s_1\le s_2\le\ldots\le s_N)，花位于 f_1,f_2,\ldots,f_M~(f_1\le f_2\le\ldots\le f_M)。洒水器的喷水强度均为 K：

若第 i 个洒水器向左旋转，它可以浇灌位于 s_i-K 到 s_i 之间的所有花；
若第 i 个洒水器向右旋转，它可以浇灌位于 s_i 到 s_i+K 之间的所有花。

问这些洒水器能否浇灌到所有的花。若能，求此时 K 的最小值及其对应的任意一种洒水器配置。

Solution

既然题目已经给我们排序好了，那我们第一眼看到的就是“最小值”，想到二分出最小 K，那么问题就在于 check() 部分如何写了。

先进行初步分类讨论（默认从左往右遍历洒水器），若某洒水器左侧的花已全部灌溉，则将其向右旋转；否则向左旋转。代码如下（删去了有关洒水器配置的部分）：
```
bool check(int &k){ //二分出的k
int j = 1;
for(int i = 1; i <= n; ++ i)
    if(j <= m && f[j] < s[i])
        if(f[j] < s[i] - k) return 0;
        else while(j <= m && f[j] <= s[i]) ++ j;
    else while(j <= m && f[j] <= s[i] + k) ++ j;
return j > m;
}
```
结果只有 9 分，需要进一步讨论，向右旋转在上述条件下已是最优选择，问题就出在向左旋转，给朕上图！图中，由于洒水器 2 必然向左旋转，从而灌溉了花 1,2，导致洒水器 1 未起到实际效益，而花 3 又空着，因此需要洒水器 1 向右旋转。

那么对于两个连续的向左旋转的洒水器 i,i+1，若洒水器 i+1 导致洒水器 i 未起到实际效益，就将 i 向右旋转。于是就有了进阶版的 check()：

bool check(int &k){
int j = 1;
for(int i = 1; i <= n; ++ i)
    if(j <= m && f[j] < s[i])
        if(f[j] < s[i] - k) return 0;
        else{
            int fp = f[j];
            while(j <= m && f[j] <= s[i]) ++ j;
            if(j <= m && i < n && f[j] < s[i + 1] && fp >= s[i + 1] - k){
                while(j <= m && f[j] <= s[i] + k) ++ j;
                ++ i;
            }
        }
    else while(j <= m && f[j] <= s[i] + k) ++ j;
return j > m;
}

获得了 73 分（仅 UKE 了一个点），接着上图！这张图是前一张图的衍生版。有了前车之鉴，我们不难想到洒水器 2 需要向右旋转，并且前一张图的配置方式不能延用。

那么问题来了——这显然与代码的逻辑相悖。再尝试几次之后可以发现，每次某一个洒水器的向左旋转都有可能导致前面所有的洒水器的朝向反转。

因而对于 A 个连续的向左旋转的洒水器，这种反转可能会出现 \left(A-1\right) 次，且最终结果取决于最后一次，那么我们只要将每次会反转的洒水器打好标记，再从右到左反转一遍即可，具体看下方代码。
注意这题的 K,s_i,f_i 都可以取到 0。

代码时间复杂度 \mathcal O\left((N+M)\log T\right)，其中 T 为 K 的值域。

Code

#include <iostream>
using namespace std;
const int N = 100005;
int n, m, s[N], sp[N], f[N], lft = 0, rt = 1e9, ans = -1;
bool c[N];
string out, plan;
int read(){
    int x = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return x;
}
void write(int x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
bool check(int &k){
    plan = "";
    int j = 1;
    for(int i = 1; i <= n; ++ i)
        if(j <= m && f[j] < s[i])
            if(f[j] < s[i] - k) return 0;
            else{
                sp[i] = f[j];
                while(j <= m && f[j] <= s[i]) ++ j;
                if(plan.back() == 'L' && sp[i - 1] >= s[i] - k){
                    c[i] = 1;
                    while(j <= m && f[j] <= s[i - 1] + k) ++ j;
                }
                plan.push_back('L');
            }
        else{
            while(j <= m && f[j] <= s[i] + k) ++ j;
            plan.push_back('R');
        }
    if(j <= m) return 0;
    out = plan;
    for(int i = n; i >= 1; i --) if(c[i]) c[i] = c[i - 1] = 0, out[i - 2] = 'R';
    return 1;
}
int main(){
    n = read(), m = read();
    for(int i = 1; i <= n; ++ i) s[i] = read(); //洒水器
    for(int i = 1; i <= m; ++ i) f[i] = read(); //花
    while(lft <= rt){
        int mid = (lft + rt) >> 1;
        if(check(mid)) rt = mid - 1, ans = mid;
        else lft = mid + 1;
    }
    if(ans == -1) return fputs("-1", stdout), 0;
    write(ans), putchar('\n');
    fputs(out.c_str(), stdout);
    return 0;
}