e464 - Error
題目描述
題目要求給定一個距離 r 和 n 個點的位置 a[i]，求最少需要多少個工人才能覆蓋所有點。工人可以覆蓋距離在 r 以內的點。
解題思路
這題可以使用貪心演算法和二分搜尋來解決。首先，將點的位置排序。然後，使用二分搜尋來尋找最少需要的工人數量。對於每個工人數量 m，我們使用貪心策略來判斷是否可以使用 m 個工人覆蓋所有點。貪心策略是從第一個點開始，盡可能地用一個工人覆蓋最多的點。如果無法用 m 個工人覆蓋所有點，則增加工人數量，否則減少工人數量。
複雜度分析
- 時間複雜度: O(n log n + n log n) = O(n log n)，其中 O(n log n) 是排序的複雜度，O(n log n) 是二分搜尋的複雜度。
- 空間複雜度: O(n)，用於儲存點的位置。
程式碼
#include <bits/stdc++.h>
using namespace std;
long long n,r,a[200005];
bool ok(long long m){
int la=1;
while(a[la]-a[0]<=r)++la;
--la;
--m;
for(int i=la+1;i<n;++i){
if(a[i]-a[la]>r){
if(--m<0)return 0;
int ti=i;
while(i<=n&&a[i]-a[ti]<=r)++i;
--i;
la=i;
}
}
return 1;
}
long long bs(long long l,long long r){
if(l>r)return l;
long long m=(l+r)/2;
return (ok(m)?bs(l,m-1):bs(m+1,r));
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
while(cin >> r >> n){
if(n==-1&&r==-1)return 0;
if(r<0)r=0;
if(n<=0){
cout << "0\n";
continue;
}
else if(n==1){
cout << "1\n";
continue;
}
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
cout << bs(1,n) << "\n";
}
return 0;
}