bzoj4525: [Usaco2016 Jan]Angry Cows

二分。

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 50000 + 10; int n,k,l,r,mid,ans,d;
int a[maxn]; bool check(int dist) {
dist=2*dist;
int d=0,sum=1;
for(int i=2;i<=n;i++) {
if(a[i]-a[i-1]>dist-d) {
sum++;
d=0;
}
else d+=a[i]-a[i-1];
}
//printf("%d %d\n",dist/2,sum);
return sum<=k;
} int main() {
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
l=1;r=a[n];
while(l<r) {
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
printf("%d\n",l);
return 0;
}
上一篇:BITED数学建模七日谈之七:临近比赛时的准备工作


下一篇:gitignore样例解析