Zerojudge c575
題敘
https://zerojudge.tw/ShowProblem?problemid=c575
一個一維座標上有 $n$ 個點 $p$，在座標上最多放置 $k$ 個基地台
每個基地台可以隨意放在座標點上任一點(不限於整數座標)，若點包含於某基地台的半徑 $r$ 內則可接收到訊號
求基地台的最小直徑，使得所有標記的點都能接收到訊號
想法
點可以說幾乎無限多個，顯然暴力去找基地台可以放在哪裡是不合理的
但是我們知道基地台可以隨便放，也知道需要包含在那些座標點上
我們可以先將所有座標點由小到大排序
很快可以知道基地台最大直徑為$p_n-p_1$，最小為1(一個點座標長度)
二分搜基地台的直徑 $R$ ，每次檢查 $R$ 是否符合
至於要如何檢查呢?
我們可以從 $p_1$ 開始，每次加上本次枚舉的直徑，將包含在直徑內的點都移除，並每次紀錄使用基地台數量
當基地台數量超過 $k$ 就不符合
補充
其實可以發現，基地台直徑最大為 $(p_n-p_1)/k$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
#include<bits/stdc++.h>
#define LL long long
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define pii pair<int,int>
using namespace std;
long long n,k,base[50005];
bool ok(int len){
int numbers=0;
for(int i=0,now=base[0]+len ; i<n && numbers<=k+1 ; ){
now=base[i]+len;
numbers++;
while(i<n && base[i]<=now)
i++;
}
if(numbers<=k)
return true;
else
return false;
}
int main(){
IOS
cin>>n>>k;
for(int i=0 ; i<n ; i++){
cin>>base[i];
}
sort(base,base+n);
int low=1,high=(base[n-1]-base[0])/k+1;
while(low<high){
int mid=(low+high)>>1;
if(ok(mid))
high=mid;
else
low=mid+1;
}
cout<<low<<"\n";
return 0;
}
|
複雜度
二分搜時間複雜度為 $O(log(high-low))$
本題 $high-low$ 最大不超過 $10^6$