首先对heater进行排序,对于每个house,我们尝试用二分的方式寻找它两端的heater去覆盖,取其中最小的,再与答案取最大值以求将每个house都覆盖到。
对于端点我们需要采取特殊处理,即左端点用最小的heater去覆盖,右端点用最大的heater去覆盖。
#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<c;++a)
#define MAXN 25000
using namespace std;
int n,m;
vector<int> heaters;
vector<int> houses;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
heaters.resize(m);
houses.resize(n);
int temp;
f(i,0,n) {
cin >> temp;
houses.push_back(temp);
}
f(i,0,m) {
cin >> temp;
heaters.push_back(temp);
}
sort(heaters.begin(),heaters.end());
int ans = INT_MIN;
for(auto house : houses) {
auto pos = lower_bound(heaters.begin(),heaters.end(),house);
auto dist1 = (pos == heaters.end()) ? INT_MAX : *pos - house;
auto dist2 = (pos == heaters.begin()) ? INT_MAX : house - *(--pos);
ans = max(ans,min(dist1,dist2));
}
cout << ans << endl;
return 0;
}