2018-2-6

直接使用二分搜索即可，如果可以滿足條件的話，就在mid與high之間，否則的話就在low與mid之間。

在判斷給定的d是否能夠滿足條件時(shí)，我用的是貪心的想法，就是讓牛盡可能的朝左邊的牛棚中去，這樣很容易就可以判斷出來(lái)。

#include<iostream> #include<algorithm> #include<cstdio> using namespace std;const int N = 100000; int x[N+1]; int n,c,cnt;bool res(int d){cnt=1;int e=x[1];for (int i=2;i<=n;i++){if (x[i]-e>=d){cnt++;e=x[i];}}return cnt>=c; }void div(){int l=0,h=x[n]-x[1];while (h-l>1){int m=(l+h)/2;if (res(m)) l=m;else h=m;}cout<<l<<endl; }int main(){while (cin>>n>>c){for (int i=1;i<=n;i++){scanf ("%d",x+i);}sort(x+1,x+n+1);div();}return 0; }

其實(shí)我一直有一個(gè)疑問，就是在二分搜索中，high什么時(shí)候等于mid，什么時(shí)候等于mid-1，low什么時(shí)候等于mid，什么時(shí)候等于mid+1，返回的值什么時(shí)候等于mid，什么時(shí)候等于high，什么時(shí)候等于low……

總結(jié)

以上是生活随笔為你收集整理的poj2456 二分搜索 挑战程序设计竞赛的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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