poj 3258 River Hopscotch (二分）

题目：http://poj.org/problem?id=3258

题意：

一条河长度为 L，河的起点(Start)和终点(End)分别有2块石头，S到E的距离就是L。

河中有n块石头，每块石头到S都有唯一的距离

问现在要移除m块石头（S和E除外），每次移除的是与当前最短距离相关联的石头，要求移除m块石头后，使得那时的最短距离尽可能大，输出那个最短距离。

代码：

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 using namespace std;
 5 __int64 a[50010];
 6 int n,m;
 7 bool cmp(__int64 a,__int64 b)
 8 {
 9     return a<b;
10 }
11 int juge(__int64 mid)
12 {
13     int i;
14     __int64 sum=0;
15     int num=0;
16     for(i=1;i<=n-1;i++)
17     {
18         if(sum+(a[i]-a[i-1])<=mid)
19         {
20             sum+=a[i]-a[i-1];
21             num++;
22         }
23         else
24         {
25             sum=0;
26         }
27     }
28     if(num<=m)
29     return 1;
30     else
31     return 0;
32 }
33 int main()
34 {
35     __int64 l;
36 
37     while(scanf("%I64d%d%d",&l,&n,&m)!=EOF)
38     {
39         int i;
40         a[0]=0;
41         for(i=1;i<=n;i++)
42         {
43             scanf("%I64d",&a[i]);
44         }
45         a[i]=l;
46         n=i+1;
47         sort(a,a+n,cmp);
48         /*for(i=0;i<n;i++)
49         {
50             printf("%I64d ",a[i]);
51         }
52         cout<<endl;*/
53         __int64 low=l;
54         __int64 high=l;
55         __int64 d;
56         for(i=0;i<n-1;i++)
57         {
58             d=a[i+1]-a[i];
59             if(d<low)
60             low=d;
61         }
62         //cout<<low<<" "<<high<<endl;
63         __int64 mid;
64         while(low<=high)
65         {
66             mid=(low+high)/2;
67             if(juge(mid))
68             low=mid+1;
69             else
70             high=mid-1;
71         }
72         cout<<low<<endl;
73     }
74     return 0;
75 }