https://vjudge.net/problem/POJ-2456

二分，從最大長度開始，不斷折半試，如果牛全放下了，就是可行，修改下界，否則改上屆。

1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #include<map> 8 #define lson l, m, rt<<1 9 #define rson m+1, r, rt<<1|1 10 #define INF 0x3f3f3f3f 11 typedef unsigned long long ll; 12 using namespace std; 13 int n, m, a[100010]; 14 int C(int x) 15 { 16 int pre=0, ans=1; 17 for(int i = 1; i < n; i++){ 18 while(i < n&&a[i]-a[pre]<x){ 19 i++; 20 } 21 if(i>=n) break; 22 ans++; 23 pre = i; 24 } 25 return ans >= m; 26 } 27 int main() 28 { 29 while(~scanf("%d%d", &n, &m)){ 30 for(int i = 0; i < n; i++){ 31 scanf("%d", &a[i]); 32 } 33 sort(a, a+n); 34 int lb = 0, ub = INF; 35 while(ub-lb>1){ 36 int mid = (ub+lb)/2; 37 if(C(mid)){ 38 lb = mid; 39 } 40 else ub = mid; 41 } 42 printf("%d\n", lb); 43 } 44 return 0; 45 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Surprisezang/p/9027822.html

總結(jié)

以上是生活随笔為你收集整理的poj2456 Aggressive cows（二分查找）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。