自动搬运

查看原文

来自洛谷，原作者为

	AcceptedC 暴力出奇迹，骗分过样例，暴搜挂着机，打表出省一

搬运于2025-08-24 21:18:04，当前版本为作者最后更新于2025-03-20 22:15:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

解析

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

• $\alpha=0$ 时，找与第一个塔的距离。
• $\alpha=m$ 时，此时需要找与最后一个塔的距离。
• 对于其他情况，找最近的信号塔。
  • 记得开 long long。

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

代码

#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;
}

死亡回放（提交记录）