本文主要是介绍poj3258，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题目：一条长L的河上,除了起点和终点还有N个石子，分别距离起点距离di，求去掉M个石子后相邻的最小距离的最大值
代码：
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int D[50005];
int L,N,M;
bool judge(int d){
int i,st,en,sum;
st=sum=0;
for(i=1;i<=N;i++){
en=st+1;
while(en<=N+1&&D[en]-D[st]<d)
en++,sum++;
if(sum>M) //判断删除的个数是否满足M个
return 0;
st=en;
}
return 1;
}
int main(){ //最大化最小值，用二分处理
int i,j,l,r,mid;
while(scanf("%d%d%d",&L,&N,&M)!=EOF){
for(i=1;i<=N;i++)
scanf("%d",&D[i]);
D[0]=0,D[N+1]=L;
sort(D,D+N+2);
l=r=L;
for(i=1;i<=N+1;i++) //初始值不能设成0和INF会有10 0 0这类的数据
l=min(l,D[i]-D[i-1]);
while(r-l>1){
mid=(l+r)/2;
if(judge(mid))
l=mid;
else
r=mid;
}
printf("%d\n",l);
}
return 0;
}
这篇关于poj3258的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
