POJ 3258 River Hopscotch 二分查找

题意：一条长为l（1~1,000,000,000）的河中，有n(1~50,000)块可垫脚的石头（不包括起始点和终点的），给出它们与起始点的距离rock[i]，现在要你移除其中的m块，使得具有最小间距的相邻两块石头之间的距离最大。

View Code

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 int cmp(const int &a,const int &b)
 6 {
 7     return a<b;
 8 }
 9 int m,n,l;
10 int rock[50005];
11 int dis[50005];
12 int judge(int mid)
13 {
14     int i;
15     int len;
16     int num;
17     num = len = 0;
18     for(i = 1;i <= n+1;i++)
19     {
20         if(len+dis[i] <= mid)
21         len+=dis[i],num++;
22         else
23         len = 0;
24     }
25 
26     if(num <= m)
27     return 0;
28     return 1;
29 }
30 int main()
31 {
32     int i;
33     while(cin>>l>>n>>m)
34     {
35         rock[0] = 0,rock[n+1] = l;
36         for(i = 1;i <= n;i++)
37         cin>>rock[i];
38         sort(rock+1,rock+n+1,cmp);
39         int low,high;
40         low = l;
41         high = l;
42         for(i = 1;i <= n+1;i++)
43         {
44             dis[i] = rock[i]-rock[i-1];
45             if(low > dis[i])
46             low = dis[i];
47         }
48 
49         int mid = (high+low)/2;
50 
51         while(low <= high)
52         {
53             if(judge(mid))
54             high = mid-1;
55             else
56             low = mid+1;
57             mid = (low+high)/2;
58         }
59         cout<<low<<endl;
60     }
61     return 0;
62 }