題目鏈接：http://115.159.40.116/problem_show.php?pid=5177

題目描述

農夫 John 建造了一座很長的畜欄，它包括N (2 <= N <= 100,000)個隔間，這些小隔間依次編號為x1,...,xN (0 <= xi <= 1,000,000,000).
但是，John的C (2 <= C <= N)頭牛們并不喜歡這種布局，而且幾頭牛放在一個隔間里，他們就要發生爭斗。為了不讓牛互相傷害。John決定自己給牛分配隔間，使任意兩頭牛之間的最小距離盡可能的大，那么，這個最大的最小距離是什么呢？

輸入

有多組測試數據，以EOF結束。
第一行：空格分隔的兩個整數N和C
第二行——第N+1行：分別指出了xi的位置

輸出

每組測試數據輸出一個整數，滿足題意的最大的最小值，注意換行。

樣例輸入

5 3 1 2 8 4 9

樣例輸出

3

分析：這是一個最小值最大化的問題。先對隔間編號從小到大排序，則最大距離不會超過兩端的兩頭牛之間的差值，最小值為0。所以我們可以通過二分枚舉最小值來求。假設當前的最小值為x，如果判斷出最小差值為x時可以放下C頭牛，就先讓x變大再判斷；如果放不下，說明當前的x太大了，就先讓x變小然后再進行判斷。直到求出一個最大的x就是最終的答案。

實現一：

#include<iostream> #include<cstdio> #include<algorithm> #define M 100000+5 #define INF 0x3f3f3f3f //#include <bits/stdc++.h> using namespace std;int n,m; int a[M];bool judge(int x){int last=a[0],cow=1;for(int i=1;i<n; ++i){if(a[i]-last >= x){cow++;last=a[i];if(cow>=m) return true;}}return false; } int bi_search(){int l=0,r=a[n-1]-a[0];while(l<=r){int mid=(r+l)/2;if(judge(mid)) l=mid+1;else r=mid-1;}return l-1; }int main(){while(scanf("%d%d",&n, &m)!=EOF){for(int i=0; i<n; ++i){scanf("%d",&a[i]);}sort(a,a+n);printf("%d\n",bi_search());}return 0; }

實現二（比上一個快點）：

#include<iostream> #include<cstdio> #include<algorithm> #define Max 100000+5 #define INF 0x3f3f3f3f //#include <bits/stdc++.h> using namespace std;int N,M; int a[Max];bool C(int d){int last=0;for(int i=1; i<M; ++i){int crt=last+1;while(crt<N && a[crt]-a[last]<d) crt++;if(crt==N) return false;last=crt;}return true; }int main(){while(scanf("%d%d", &N,&M)!=EOF){for(int i=0;i<N; ++i){scanf("%d",&a[i]); }sort(a,a+N);int l=0,r=INF;while(r-l>1){int mid=(r+l)/2;if(C(mid)) l=mid;else r=mid;}printf("%d\n",l);}return 0; }

資料鏈接：http://blog.csdn.net/lyhvoyage/article/details/23261973

總結

以上是生活随笔為你收集整理的NYOJ 5177 疯牛(最大化最小值 二分搜索)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。