大家好，我是小码匠。
早晨跟妈妈吐槽老码农。晚上10点40还摁着亲闺女刷题，这老爸当的。。。
昨天到家本来就晚，都10点了，然后作业还没写完，我快速写完作业，又去洗澡，就10:40了。
随口问了句老码农，老码农尽然还问：有没有兴趣再刷一道题。
一听我就没好气，刷，我到11点就睡觉。。。
前置知识
- 二分查找
路漫漫其修远兮，吾将上下而求索
离自己的既定目标：
- 目标：300道
- 已完成：21道
- 待完成：279道
题目地址
- https://www.luogu.com.cn/problem/CF702C
在直线上给出n个城市的位置(x坐标)和在同一直线上的m个蜂窝塔的位置(x坐标)。所有的塔都以同样的方式工作——它们为所有城市提供蜂窝网络，这些城市位于离塔不超过r的距离处才能被蜂窝网络覆盖。
你的任务是找出使得每个城市都能被蜂窝网络覆盖的最小r值，即每个城市在距离r的范围内至少有一个蜂窝塔。
如果r=0，则塔仅为其所在的位置提供蜂窝网络。一个塔可以为任意数量的城市提供蜂窝网络，但是所有这些城市都必须在距离塔不超过r的距离上。
输入格式
- 第一行包含两个正整数n和m，表示有n个城市与m个蜂窝塔。
- 第二行包含n个整数a[1],a[2]...a[n]，表示每个城市的位置(x坐标)
- 第三行包含m个整数b[1],b[2]...b[m]，表示每个蜂窝塔的位置(x坐标)
注意，允许多个城市或蜂窝塔位置相同。
输出格式
输出最小的r，使得每个城市都被蜂窝网络覆盖。
数据范围
输入输出样例
输入 #1复制
代码语言：javascript复制3 2
-2 2 4
-3 0
输出 #1复制
代码语言：javascript复制4
输入 #2复制
代码语言：javascript复制5 3
1 5 10 14 17
4 11 15
输出 #2复制
代码语言：javascript复制3
知识点
- 二分
题解
本题属于一眼二分，题解就不写了，看代码吧。
AC代码
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
const int MAX_NUM = 1e5 5;
long long a[MAX_NUM], b[MAX_NUM];
int n, m;
bool check(long long len) {
int l = 0;
int i;
int cnt = 1;
for (i = 0; i < n && l < m; i) {
while (abs(b[l] - a[i]) > len) {
l;
cnt;
}
}
return cnt <= m;
}
void best_coder() {
cin >> n >> m;
for (int i = 0 ; i < n; i) {
cin >> a[i];
}
for (int i = 0 ; i < m; i) {
cin >> b[i];
}
sort(a, a n);
sort(b, b m);
long long l = 0, r = LONG_LONG_MAX;
while (l < r) {
long long mid = l r >> 1;
if(check(mid)) {
r = mid;
} else {
l = mid 1;
}
}
cout << r;
}
void happy_coder() {
}
int main() {
// 提升cin、cout效率
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
// 小码匠
best_coder();
// 最优解
// happy_coder();
return 0;
}
学习代码：二分算法
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
// returns the first index in the array that is >= value, or arr.size() if no
// such index exists
int firstAtLeast(const vector<int> &arr, int value) {
int lo = 0, hi = arr.size();
while (lo < hi) {
int mid = (lo hi) / 2;
if (arr[mid] >= value) hi = mid;
else lo = mid 1;
}
return lo;
}
int main() {
int n, m;
cin >> n >> m;
vector<int> cities, towers;
for (int i = 0; i < n; i ) {
int city;
cin >> city;
cities.push_back(city);
}
for (int i = 0; i < m; i ) {
int tower;
cin >> tower;
towers.push_back(tower);
}
int minR = 0;
for (int i = 0; i < n; i ) {
int towerRight = firstAtLeast(towers, cities[i]);
int towerLeft = towerRight - 1;
int minRForThisCity = 2e9;
if (towerRight < m) {
assert(towers[towerRight] >= cities[i]);
minRForThisCity =
min(minRForThisCity, towers[towerRight] - cities[i]);
}
if (towerLeft >= 0) {
assert(towers[towerLeft] <= cities[i]);
minRForThisCity =
min(minRForThisCity, cities[i] - towers[towerLeft]);
}
minR = max(minR, minRForThisCity);
}
cout << minR << endl;
}
学习代码：Set，实则也是二分
代码语言：javascript复制#include <algorithm>
#include <iostream>
#include <set>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int cities[n];
set<int> towers;
int tower;
for (int i = 0; i < n; i ) { cin >> cities[i]; }
for (int i = 0; i < m; i ) {
cin >> tower;
towers.insert(tower);
}
int r = 0;
for (int i = 0; i < n; i ) {
int dist = 2e9 1;
// find closest tower to the right of the city
auto closesttower = towers.lower_bound(cities[i]);
if (closesttower != towers.end()) {
// if a tower is found, update the distance
dist = *closesttower - cities[i];
}
// find closest tower to the left of the city
if (closesttower != towers.begin()) {
closesttower--;
// update dist with the minimum of the distances
dist = min(dist, cities[i] - *closesttower);
}
r = max(r, dist);
}
cout << r << endl;
return 0;
}
END
你的每个【点赞 在看】
我都当成了喜欢
让我们同行，一起成长为优秀的oier，去改变世界。
