【題目敘述】https://zerojudge.tw/ShowProblem?problemid=c575
【解題想法】二分搜 (Binary Search)【筆記】
- 題目要求以 K 個基地台覆蓋 N 個服務點。
- 題目提供 N 個服務點的座標，但沒有按照座標大小排序。讀入測資後，先排序。
- 如果第一個服務點和最後一個服務點之間的距離 dis <= 2，不用計算，答案直接為 1。
- 否則的話，進行二分搜來決定最佳基地台間距，搜尋範圍：
- 最小 mn = 1
- 最大 mx = int(dis / k) + 1
- 每次計算中間值 mid 後，重新測試是否用 K 個基地台，就能覆蓋 N 個服務點。
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int N, K;
int P[maxn];
bool canCover(int d){
int coverage = P[0] + d;
int cnt = 1;
for (int i=1; i<N; i++){
while (P[i] > coverage){
coverage = P[i] + d;
cnt++;
}
}
return (cnt <= K);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K;
for (int i=0; i<N; i++){
cin >> P[i];
}
sort(P, P+N);
int l = 0;
int r = (P[N-1] - P[0]) / K + 1;
int mn = 2e9;
while (l < r){
int mid = (l + r) / 2;
if (canCover(mid)){
mn = mid;
r = mid;
} else {
l = mid + 1;
}
}
cout << mn << '\n';
return 0;
}
Python code
while True:
try:
n, k = map(int, input().split())
lst = list(map(int, input().split()))
lst.sort()
dis = lst[-1] - lst[0]
if dis <= 2:
print(1)
continue
mn = 1
mx = int(dis/k) + 1
while True:
mid = (mn + mx) // 2
count = 0
start = 0
for j in range(k):
dis2 = lst[start] + mid
count += 1
for l in range(start, n):
if lst[l] > dis2:
start = l
break
else:
mx = mid
break
else:
mn = mid + 1
if mn == mx:
print(mn)
break
except:
break