B4242 [海淀区小学组 2025] 蜂窝网络 题目解析

· · 题解

题目传送门

解析

显然考察二分查找，找到离它最近的一个能覆盖的信号塔就可以了，最简便的方法是使用 lower_bound，当然也可以手搓。
本题就是找到离城市最近的信号塔，根据索引 \alpha 数目可分为三种情况:

最后就是求最小覆盖半径，把每个城市与离它最近的信号塔的距离求出来，最后取最大的那个值就是覆盖所有城市的最小半径。

代码

#include<bits/stdc++.h>
#define ll long long //不开long long见祖宗
using namespace std;
int n,m;
const int maxN=1e5+10;
ll a[maxN],b[maxN];
ll ans;
ll BS(ll g){
    if(g<=b[1]) return b[1]-g;
    if(g>=b[m]) return g-b[m];
    int iL=1,iR=m;
    while(iL<iR){
        int mid=iL+(iR-iL+1)/2;
        if(b[mid]<=g) iL=mid;
        else iR=mid-1;
    }
    return min(g-b[iL],b[iL+1]-g);
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(b+1,b+m+1);
    for(int i=1;i<=n;i++){
        ans=max(ans,BS(a[i]));//最后取最大的值作为最小半径
    }
    cout<<ans;
}

死亡回放（提交记录）