瘋牛

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：4 描述

農夫 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

解題思路：我一開始的想法也是用二分，但不是二分長度，而是每次都插入兩個位置之間，但是這樣做會太繞。。。。這道題其實不需要這么麻煩，直接二分答案即可。。

AC:

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std;const int maxn = 100005; int pos[maxn],n,c;bool cmp(int a,int b) {return a < b; }bool judge(int len) {int cnt = 1, pre = 1;for(int i = 2; i <= n; i++){if(pos[i] - pos[pre] >= len){pre = i; cnt++;if(cnt == c)return true;}}return false; }void binary_search() {int l = 0, r = pos[n-1]-pos[0], mid, ans;while(l <= r){mid = (l+r)>>1;if(judge(mid)){l = mid + 1;ans = mid;}else r = mid - 1;}printf("%d\n",ans); }int main() {while(scanf("%d%d",&n,&c)!=EOF){for(int i = 1; i <= n; i++)scanf("%d",&pos[i]);sort(pos+1,pos+1+n,cmp);binary_search();}return 0; }

總結

以上是生活随笔為你收集整理的nyoj 586的全部內容，希望文章能夠幫你解決所遇到的問題。

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