POJ 3258 River Hopscotch（二分答案）

嗯...

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

一道很典型的二分答案的题目，和跳石头太像了！！

这道题的题目很显然，求最小中的最大值，注意这道题石头的位置不是从小到大输出的，所以要排序一遍...

cnt记录可以跳过的石头个数：检查答案时，如果当前石头与前一个石头之间的距离小于mid，那么直接可以跳过，所以cnt++。如果跳不过去，则更新前一块石头的位置。

如果移走的石头数目小于等于m，说明跳的距离必须或者还可能更大，所以l = mid + 1；否则则要r = mid - 1...（这道题好像没有卡终点...

AC代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 
 6 using namespace std;
 7 
 8 int len, m, n, a[500005];
 9 
10 inline int check(int x){
11     int cnt = 0, last = 0;
12     for(int i = 1; i <= n + 1; i++){
13         if(a[i] - a[last] < x) cnt++;
14         else last = i;
15     }
16     if(cnt <= m) return 1;
17     return 0;
18 }
19 
20 int main(){
21     while(scanf("%d%d%d", &len, &n, &m) != EOF){
22         memset(a, 0, sizeof(a));
23         a[n + 1] = len;
24         for(int i = 1; i <= n; i++){
25             scanf("%d", &a[i]);
26         }
27         sort(a + 1, a + n + 1);
28         int l = 1, r = len, ans;
29         while(l <= r){
30             int mid = (l + r) >> 1;
31             if(check(mid)) {ans = mid; l = mid + 1;}
32             else r = mid - 1;
33         }
34         printf("%d
", ans);
35     }
36     return 0;
37 }

AC代码