題目大意#
給你數線上幾個服務點，請你任意設置k個基地點，並找出能全部服務點都被服務到的最小直徑
解題過程#
首先我們先思考，確定直徑的時候如何最小化建造基地的數量?
我們可以發現，假設\(1\)有服務點，並不知道其他點在何處，僅知道\(1\)左邊已經無服務點，且服務直徑為\(3\)，那麼我們可以在\(2\)建造基地台，這樣就會服務到1的前提下，能涵蓋右邊最多的範圍。
如此想來可以發現，如果我們從左往右跑，遇到服務點，就以他為左界建造一個基地台，讓他在涵蓋該服務點的前提，能往右涵蓋最多範圍，再往下搜尋，遇到還沒被服務的點，再以前面的規則建造基地台，就可以使基地台數量最小。
於是我們可以寫出這樣的函式來計算在服務直徑為\(r\)的狀態下，所需要建造的最小基地台數量。(注意題目給的服務點無由小排到大，記得先排序方便從左邊跑到右邊)
int ck(int r, vector<int> &v){
int last=-1, res =0;
for(int x=0; x<v.size(); x++){
if(last >= v[x]) continue; //這個點還在上個基地台服務範圍，跳過
last = v[x] + r; //紀錄上個基地台服務範圍右界
res++; //所需基地台數量
}
return res;
}
接著我們思考如何解決題目問題
我們知道如果服務半徑越大，那麼所需的基地台數量就越少，於是我們可以將服務半徑由\(1\)列到\(10^9\)，對應他們所需的基地台數量，這樣基地台數量就會是一個遞減數列。
於是我們可以對基地台數量二分搜，找到 所需基地台數量 \( \le k\)的前提下，服務半徑的最小值，也就是這個數列中符合條件最左邊的點。
利用上面的函式寫出AC解!
AC Code#
#include <bits/stdc++.h>
using namespace std;
int ck(int r, vector<int> &v){
int last=-1, res =0;
for(int x=0; x<v.size(); x++){
if(last >= v[x]) continue;
last = v[x] + r;
res++;
}
return res;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n, k;
cin >> n >> k;
vector<int> v(n);
for(int x=0; x<n; x++) cin >> v[x];
sort(v.begin(), v.end());
int l=0, r=1e9;
while(l + 1< r){
int mid = (l+r) >> 1;
if(ck(mid, v) > k) l = mid;
else r = mid;
}
cout << r;
return 0;
}
