题目描述

难度分:$1500$

输入$n,m(1 \leq n,m \leq 10^5)$和长分别为$n$和$m$的非递减数组$a$和$b$，元素范围在$[-10^9,10^9]$。

在一维数轴上，数组$a$表示每个城市的位置，数组$b$表示每座信号塔的位置。

问：信号塔发射信号的半径至少是多少，才能使所有城市都被信号覆盖？

输入样例$1$

3 2
-2 2 4
-3 0

输出样例$1$

4

输入样例$2$

5 3
1 5 10 14 17
4 11 15

输出样例$2$

3

算法

二分答案+双指针

信号塔的辐射半径越大肯定更容易覆盖城市，因此很容易发现单调性，可以用二分答案来求得最小覆盖半径。

二分答案的框架很简单，对于一个指定的半径$radius$：

1. 如果这个半径能够使得信号塔覆盖所有城市，就记录答案，往左搜索看半径能不能更少；
2. 否则半径就太小了，往右搜索更大的半径。

关键在于如何写二分的$check$，可以用双指针来求解。令$i=1$遍历$b$数组，$l=r=1$遍历$a$数组，此时如果满足$|b[i]-a[r]| \leq radius$，就说明$i$信号塔能够覆盖右边界城市$r$，不断扩张右边界，直到$r \gt n$或者$|b[i]-a[r]| \gt radius$，这时候信号塔$i$就不能再覆盖更多的城市了，应该令$l=r$考虑下一个信号塔$i+1$能覆盖的范围。如果在整个过程中$r \gt n$可以达成，说明所有城市都能被覆盖，否则不能。而指针$i$、$l$、$r$都是不会回退的，因此时间复杂度是线性的。

复杂度分析

时间复杂度

二分答案的时间复杂度为$O(log_2A)$，$A$仅跟城市和信号塔的最远距离有关，本题中$A=2 \times 10^9$。而$check$的双指针算法时间复杂度是$O(n+m)$，因此算法整体的时间复杂度为$O((n+m)log_2A)$。

空间复杂度

仅使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
int n, m, a[N], b[N];

bool check(int radius) {
    int l = 1, r = 1;
    for(int i = 1; i <= m; i++) {
        if(abs(b[i] - a[l]) <= radius) {
            while(r <= n && abs(b[i] - a[r]) <= radius) r++;
            if(r <= n) {
                l = r;
            }else {
                break;
            }
        }
    }
    return r > n;
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    int l = 0, r = 2e9;
    while(l < r) {
        int mid = l + ((r - l)>>1);
        if(check(mid)) {
            r = mid;
        }else {
            l = mid + 1;
        }
    }
    printf("%d\n", r);
    return 0;
}