P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G——题解

解题思路

先排序牛舍位置。二分候选最小距离 $d$，从最左牛舍开始贪心放牛，之后每次选择第一个与上一头牛距离至少为 $d$ 的牛舍。若能放够 $m$ 头，说明 $d$ 可行。

复杂度分析

排序 $O(n\log n)$，二分检查 $O(n\log(x_{max}-x_{min}))$，空间 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n,m;cin>>n>>m;vector<long long>x(n);for(auto &v:x)cin>>v;sort(x.begin(),x.end());
    auto ok=[&](long long d){int cnt=1;long long last=x[0];for(int i=1;i<n;i++)if(x[i]-last>=d){cnt++;last=x[i];}return cnt>=m;};
    long long lo=0,hi=x.back()-x.front(),ans=0;
    while(lo<=hi){long long mid=(lo+hi)/2;if(ok(mid))ans=mid,lo=mid+1;else hi=mid-1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int n,m;cin>>n>>m;vectorx(n);for(auto &v:x)cin>>v;sort(x.begin(),x.end()); auto ok=[&](long long d){int cnt=1;long long last=x[0];for(int i=1;i<n;i++)if(x[i]-last>=d){cnt++;last=x[i];}return cnt>=m;}; long long lo=0,hi=x.back()-x.front(),ans=0; while(lo<=hi){long long mid=(lo+hi)/2;if(ok(mid))ans=mid,lo=mid+1;else hi=mid-1;} cout<<ans<<'\n';return 0; }