POJ 2456 Aggressive cows 二分
来源：http://poj.org/problem?id=2456
题意：有n个点，在一条直线上，座标已知。现在要把m头牛放在一些点上，问这些牛之间的最小距离最大是多少。
思路：二分答案。
代码：
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;const int N = 100010;int num[N];int main(){//freopen("1.txt","r",stdin);int n,c;while(scanf("%d%d",&n,&c) != EOF){ num[0] = 0; for(int i = 1; i <= n; ++i) scanf("%d",&num[i]); sort(num,num+n+1); int lp = 1,rp = num[n],ans = 0; while(lp < rp){ int mmid = (lp + rp) / 2; int cnt = 1,pos = 0,ji = 1; while(1){ int low = lower_bound(num+1,num+n+1,pos + mmid + ji) - num; if(low > n) break; cnt++; ji = 0; pos = num[low]; } if(cnt < c) rp = mmid ; else{ ans = mmid; lp = mmid + 1; } } printf("%d\n",ans);}return 0;}