本文主要是介绍POJ3258（二分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
有一群牛要过河，河长L，河中有N块石头，每块石头离河边Di远，现在要去掉M块石头，求剩下的石头之间以及石头与河岸的最小距离的最大值。
题解：
看代码。
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int MAXN=50000+10;
int L,n,m;
int a[MAXN];
int check(int x)
{int k=0,i=1,last=0;for(i=1;i<=n+1;i++)if(a[i]-a[last]<x)//注意这里是用前面的石头跟后面的石头计算距离（起点是在河边的，你不可能一开始就删除河边吧？） k++;elselast=i;//如果两个石头之间的距离大于二分出来的答案的话，就保存下来，与下一块石头计算距离 if(k>m)return 1;elsereturn 0;
}
int erfen()
{int l=0,r=L,ans=0;while(r>=l){int mid=(l+r)/2;if(check(mid))//如果删除的石头大于m的话，就说明最小距离过大了 r=mid-1;else {ans=mid;l=mid+1;}}return ans;
}
int main()
{while(~scanf("%d%d%d",&L,&n,&m)){memset(a,0,sizeof(a));for(int i=1;i<=n;i++)scanf("%d",&a[i]);a[0]=0;//开始的点 a[n+1]=L;//终点 sort(a,a+n+2);//把始点和终点放进去。 printf("%d\n",erfen());}
}这篇关于POJ3258（二分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
