扫地机器人

题目概要

数轴上有 \(n\) 个扫地机器人和 \(m\) 个垃圾，\(i\) 号机器人的初始坐标是 \(a_i\)（\(1 \le i \le n\)），第 \(j\) 个垃圾的坐标是 \(b_j\)（\(1 \le j \le m\)）。

扫地机器人每秒的移动距离是 \(1\)，分为三个种类：

1 类机器人只能向左移动，也就是说如果现在有一个 1 类机器人位于坐标 \(x\)，那么一秒后它位于坐标 \(x-1\)；
2 类机器人只能向右移动，也就是说如果现在有一个 2 类机器人位于坐标 \(x\)，那么一秒后它位于坐标 \(x+1\)；
3 类机器人可以自己选择向左或向右移动，随时可以改变方向且改变方向不花时间，也就是说如果现在有一个 3 类机器人位于坐标 \(x\)，那么一秒后它可能位于坐标 \(x-1\) 或坐标 \(x+1\)。

一个垃圾被任意一个扫地机器人经过时会被清理，清理垃圾不花时间。多个扫地机器人可以同时位于一个坐标。

求清理所有垃圾最少需要花多少秒。数据保证至少有一个 3 类机器人。

\(1 \le n \le 10^5\)
\(1 \le m \le 2 \times 10^5\)
\(1 \le a_i, b_j \le 10^{18}\)

解法

考虑二分答案。我们来尝试解决下述问题

给定非负整数 \(k\)，判断能否在 \(k\) 秒之内清理所有垃圾。

只能向左移动和只能向右移动的机器人，它们在 \(k\) 秒内的清理范围是确定的。我们先把能被它们清理的垃圾标记掉，然后判断第三类机器人能否在 \(k\) 秒内清理完剩余的垃圾。

按初始位置从左到右的顺序考虑每个第三类机器人。先考虑最左边那个第三类机器人，如果它左边没有尚未清理的垃圾，那么它就一直向右移动。如果它左边还有尚未清理的垃圾，不难看出，这些垃圾最好是由它来清理。这时我们还需要判断

这个扫地机器人是先往左走再往右走，还是先往右走再往左走？

往左走需要走到哪里是确定的，我们可以算出

先往左走的话，往右最多移动多少距离；
先往右走的话，往右最多移动多少距离。

哪种走法往右能够移动的距离更多，就怎样走。具体的，设最左边那个第三类机器人和最左边尚未清理的垃圾之间的距离是 \(d\)。首先要有 \(d \le k\)，否则不可能在 \(k\) 秒内清理那个垃圾。

若先往左走，往右最多移动 \(k - 2d\)，
若先往右走，往右最多移动 \((k - d) / 2\)。

这样，我们就能决定最左边那个第三类机器人怎么走。我们跳过能被它清理的垃圾，然后考虑下一个第三类机器人。

代码

const int maxm = 2e5 + 5;
long long b[maxm];
bool vis[maxm];
int n, m;
vector<long long> pos[4];

bool check(long long k) {
    memset(vis, 0, sizeof vis);
    // 把第一类机器人能清理的垃圾标记掉
    int ptr = 0;
    for (long long x : pos[1]) {
        while (ptr < m && b[ptr] <= x) {
            if (b[ptr] >= x - k)
                vis[ptr] = true;
            ptr++;
        }
    }
    // 把第二类机器人能清理的垃圾标记掉
    ptr = 0;
    for (long long x : pos[2]) {
        while (ptr < m && b[ptr] <= x + k) {
            if (b[ptr] >= x)
                vis[ptr] = true;
            ptr++;
        }
    }
    // 检查第三类机器人
    ptr = 0;
    for (long long x : pos[3]) {
        while (ptr < m && vis[ptr])
            ptr++;
        if (ptr == m)
            return true;
        if (b[ptr] + k < x)
            return false;
        long long d = max(0LL, x - b[ptr]);
        long long t = max(k - 2 * d, (k - d) / 2);
        while (ptr < m && b[ptr] <= x + t)
            ptr++;
    }
    while (ptr < m) {
        if (!vis[ptr]) return false;
        ptr++;
    }
    return true;
}

int main() {
    // 输入
    cin >> n >> m;
    vector<long long> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;
        pos[type].push_back(a[i]);
    }
    for (int i = 0; i < m; i++)
        cin >> b[i];
    // 排序
    for (int i = 1; i <= 3; i++)
        sort(pos[i].begin(), pos[i].end());
    sort(b, b + m);
    // 二分答案
    long long ok = 2e18, ng = -1;
    while (ok - ng > 1) {
        long long x = (ok + ng) / 2;
        if (check(x))
            ok = x;
        else
            ng = x;
    }
    cout << ok << '\n';
}