Noip 2015 Day2 T1 跳石头

Noip 2015 senior Day2 跳石头

这道题是一道很经典的二分。

这点我们在当初学习的时候就有提到过。

然后这次我们依旧是二分寻找。

二分判断距离。

我们写的Check函数，判断的是距离，也就是说我们每一次对距离判断，那么再该距离下我们能去除多少个石头，然后如果多了我们往左找，少了往右找。

其余的就没什么好讲的了。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 #define N 50010
 8 
 9 int l,n,m;
10 int rock[N];
11 
12 bool check(int distance)
13 {
14     int sum = m, last_point = 0;
15     for(int i=1;i<n;i++)
16     {
17         if(rock[i] - rock[last_point] < distance)
18             sum--;
19         else
20             last_point = i;
21     }
22     return sum >= 0;
23 }
24 
25 void two_devide()
26 {
27     int left = 0, right = l + 10;
28     while(left + 1 < right)
29     {
30         int mid = (left + right) >> 1;
31         if(check(mid))
32             left = mid;
33         else
34             right = mid;
35     }
36     printf("%d",left);
37 }
38 
39 int main()
40 {
41     freopen("stone.in","r",stdin);
42     freopen("stone.out","w",stdout);
43     
44     scanf("%d %d %d",&l,&n,&m);
45     for(int i=1;i<=n;i++) scanf("%d",&rock[i]);
46     rock[++n] = l;
47     n++;
48     two_devide();
49     
50     return 0;
51 }