e616 - Aggressive cows
題目描述
題目要求在給定的 N 個隔間位置和 C 隻牛的情況下，找到牛之間的最大最小距離。換句話說，我們要找到一個距離 d，使得至少可以放置 C 隻牛，且任意兩隻牛之間的距離都大於等於 d。
解題思路
本題可以使用二分搜尋法來解決。首先，將隔間位置排序。然後，二分搜尋可能的最小距離範圍。對於每個可能的距離，檢查是否可以放置 C 隻牛，使得任意兩隻牛之間的距離都大於等於該距離。如果可以，則更新左邊界；否則，更新右邊界。最終，左邊界就是最大的最小距離。check(k) 函數用於判斷給定距離 k 是否可行，即是否可以放置 C 隻牛，使得任意兩隻牛之間的距離都大於等於 k。
複雜度分析
- 時間複雜度: O(N log N + log(10^9))，其中 O(N log N) 是排序的時間複雜度，O(log(10^9)) 是二分搜尋的時間複雜度，每次二分搜尋需要 O(N) 的時間來檢查可行性。
- 空間複雜度: O(N)，主要用於儲存隔間位置。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int a[100001],n,c;
inline bool check(int k){
int tmp=c,s=0;
for(int i=0;i<n;++i){
if(a[i]>s){
--tmp;
s=a[i]+k;
if(tmp<=0)return 1;
}
}
return 0;
}
inline int ans(int l,int r){
if(l>r)return l;
int m=(l+r)/2;
if(check(m)==0)
return ans(l,m-1);
else
return ans(m+1,r);
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> c;
for(int i=0;i<n;++i)
cin >> a[i];
sort(a,a+n);
cout << ans(0,1000000000) << '\n' ;
}