poj-3258-River Hopscotch-二分

題意： 一條河長度為 L，河的起點(Start)和終點(End)分別有2塊石頭，S到E的距離就是L。 河中有n塊石； 輸入的每塊石頭的距離是到起點的距離。 問現在要移除m塊石頭（S和E除外），每次移除的是與當前最短距離相關聯的石頭，要求移除m塊石頭後，使得那時的最短距離盡可能大，輸出那個最短距離。 做法： 和上一道題目的做法是一樣的都是二分。 [html]   #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++)       {  www.2cto.com         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;   }