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;}