本文主要是介绍poj-3258-River Hopscotch-二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
一条河长度为 L，河的起点(Start)和终点(End)分别有2块石头，S到E的距离就是L。
河中有n块石；
输入的每块石头的距离是到起点的距离。
问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。
做法：
和上一道题目的做法是一样的都是二分。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[100100];
int n,m;
int sw(int mid)
{int s,num,i;s=0;num=0;for(i=1;i<n+2;i++){if((s=s+a[i]-a[i-1])<=mid){num++;}else{s=0;}}if(num>m)return 0;else return 1;
}
int main()
{int l,r,i,mid,end;cin>>end>>n>>m;r=end;l=end;a[0]=0;a[n+1]=end;for(i=1;i<=n+1;i++){if(i<n+1)scanf("%d",&a[i]);if(l>a[i]-a[i-1])l=a[i]-a[i-1];}mid=(l+r)/2;sort(a,a+(n+2));while(l<=r){if(sw(mid))l=mid+1;else r=mid-1;mid=(l+r)/2;}cout<<l<<endl;return 0;
}这篇关于poj-3258-River Hopscotch-二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
