題目鏈接：點擊查看

題目大意：給出n個石頭，其位置排列在一個數(shù)軸上，起點為0，終點為ed(題目會給出)，我們設(shè)兩兩石頭之間的間距的最小值為ans，問在移走m塊石頭之后，ans的最大值是多少

題目分析：做了一下午二分，突然就來感覺了，所以說平時多做做水題也是蠻不錯的嘛（逃），下限為初始時的ans，上限為ed，二分時的mid代表答案，check函數(shù)需要枚舉n塊石頭的位置，若當前兩個石頭之間的間距大于mid不做處理，若當前兩個石頭之間的間距小于mid，則刪掉后面的那塊石頭，記錄下來一共刪掉了多少個石頭，這里需要注意一下，若后面的那塊石頭被刪掉了，則枚舉下面一個石頭時，需要用到的兩個石頭之間的間距，就變?yōu)榱水斍皟蓚€石頭的間距加上之前兩個石頭的間距之和了（因為中間的那塊石頭被刪掉了），用一個temp變量記錄一下即可，最后判斷，若需要刪掉的石頭小于等于m，則是滿足條件的，否則是不滿足條件的

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=5e4+100;int ed,n,m;int a[N];bool check(int x) {int cnt=0;int temp=0;for(int i=1;i<=n+1;i++){if(a[i]-a[i-1]+temp<x){temp+=a[i]-a[i-1];cnt++;}elsetemp=0;}return cnt<=m; }int main() { // freopen("input.txt","r",stdin);while(scanf("%d%d%d",&ed,&n,&m)!=EOF){a[0]=0;a[n+1]=ed;for(int i=1;i<=n;i++)scanf("%d",a+i);sort(a,a+n+2);int l=inf,r=ed;for(int i=1;i<=n+1;i++)l=min(l,a[i]-a[i-1]);int ans;while(l<=r){int mid=l+r>>1;if(check(mid)){ans=mid;l=mid+1;}elser=mid-1;}printf("%d\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3258 River Hopscotch(二分水题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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