c575 - APCS 2017-0304-4基地台
題目描述
題目要求在給定 N 個服務點的位置，使用 K 個基地台覆蓋所有服務點，並找出最小的基地台直徑 D = 2R。
解題思路
首先，將服務點的位置排序。然後，使用二分搜尋來尋找最小的直徑 D。對於給定的直徑 D，檢查是否可以使用 K 個基地台覆蓋所有服務點。可以使用貪心策略來判斷：從左到右遍歷服務點，如果當前服務點沒有被覆蓋，則在當前服務點建立一個新的基地台，並覆蓋後續的服務點，直到無法再覆蓋更多服務點。如果需要的基地台數量小於或等於 K，則說明當前直徑 D 是可行的；否則，說明直徑 D 太小，需要增大直徑。
複雜度分析
- 時間複雜度: O(N log N + N log (a[N-1] - a[0]))，其中 N 是服務點的數量，a[N-1] - a[0] 是服務點位置的最大範圍。排序的時間複雜度為 O(N log N)，二分搜尋的時間複雜度為 O(log (a[N-1] - a[0]))，每次二分搜尋中，貪心策略的時間複雜度為 O(N)。
- 空間複雜度: O(N)，主要用於儲存服務點的位置。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long int a[50000]={0};
long long int bs (long long int min,long long int max,long long int key,int times){
long long int m = (min+max)/2;
if(min>max)
return m;
long long int sum=-1,count=0;
bool chat=1;
for(int i=0;i<key;i++){
if(a[i]>sum){
sum=a[i]+m;
count++;
}
if(count>times){
chat=0;
break;
}
}
if(chat==0)
return bs ( m+1, max, key, times);
else
return bs ( min, m-1, key, times);
}
int main(){
int N,K;
while(cin >> N >> K){
for(int i=0;i<50000;i++)
a[i]=0;
for(int i=0;i<N;i++)
cin >> a[i];
sort(a,a+N);
long long int max=a[N-1]-a[0];
cout << bs(1,max,N,K)+1 << '\n';
}
}