poj 3258 River Hopscotch 【二分】

題目真是不好讀，大意例如以下（知道題意就非常好解了）

大致題意：

一條河長度為 L，河的起點(Start)和終點(End)分別有2塊石頭，S到E的距離就是L。

河中有n塊石頭，每塊石頭到S都有唯一的距離

問如今要移除m塊石頭（S和E除外），每次移除的是與當前最短距離相關聯的石頭，要求移除m塊石頭后，使得那時的最短距離盡可能大，輸出那個最短距離。

//Memory Time 
//420K   391MS #include<iostream>
#include<algorithm>
using namespace std;int main(void)
{int L;  //河總長int n;  //河中石頭數（除起點S和終點外E）int m;  //移除石頭數while(cin>>L>>n>>m){/*Input & Initial*/int* dist=new int[n+2];  //第i塊石頭到起點石頭的距離為dist[i]dist[0]=0;    //起點Sdist[n+1]=L;  //終點Eint low=L;   //上界(一次跳躍的最短距離)int high=L;   //下界(一次跳躍的最大距離)for(int i=1;i<=n+1;i++){if(i<=n)   //僅輸入1~n，當i=n+1時僅用于尋找lowcin>>dist[i];if(low > dist[i]-dist[i-1])low=dist[i]-dist[i-1];}sort(dist,dist+(n+2));   //依據石頭到S的距離升序排列/*Binary-Search*/while(low<=high){int mid=(low+high)/2;  //對最大跳和最小跳的距離折中，二分查找mid相對于最優解是偏大還是偏小//如果mid是移除m個石頭后的最短距離int delrock=0;    //利用當前的mid值能移除的石頭數int sum=0;   //類比POJ 3273, 這里是 連續距離的累加值//當在第i個距離累加后sumfor(int i=1;i<=n+1;){if( (sum+=dist[i]-dist[i-1]) <= mid){i++;delrock++;}else   //當從第i個距離累加到i+k個距離后，若sum>mid，則k個距離作為一段{i++;sum=0;  //sum置0，從第i+k+1個距離又一次累加}}if(delrock<=m)   //本題難點之中的一個：即使delrock==m也不一定找到了最優解low=mid+1;   //用當前mid值移除的石頭數小于規定數，說明mid偏小else             high=mid-1;  //反之mid偏大}/*Output & Relax*/cout<<low<<endl;delete dist;}return 0;
}