2678 跳石头

2678 跳石头

难度：普及/提高-

题目类型：贪心/二分

提交次数：4

涉及知识：二分

题目背景

一年一度的“跳石头”比赛又要开始了!

题目描述

这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选

择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

代码：

 1 #include<iostream>
 2 using namespace std;
 3 const int maxx = 50010;
 4 int l, n, m;
 5 int d[50010];
 6 bool check(int x){
 7     int last=0, i, sum = 0;
 8     for(i = 0; i < n; i++){
 9         if(d[i]-last < x){
10             sum++;
11             continue;
12         }
13         last = d[i];
14     }
15     if(sum>m) return false;
16     return true;
17 }
18 int main(){
19     int i;
20     cin>>l>>n>>m;
21     for(i = 0; i < n; i++)
22         cin>>d[i];
23     int mid;
24     int ans = 0;
25     int r = l; l = 0;
26     while(l <= r){
27         mid = (l+r)/2;
28         if(check(mid)){
29             l = mid + 1;
30             ans  = mid;
31         }
32         else{
33             r = mid - 1;
34         }
35     }
36     cout<<ans;
37     return 0;
38 }

备注：

求最大值或最小值的题目，可以考虑对答案进行二分查找。check里体现了贪心思想，枚举确定保留前i块石头，如果第i+1块和最后一块确定保留的石头之间的距离小于许可范围，就搬走它，最后看搬走石头的数目是否在允许范围内。

之所以多提交了几次，是想研究一下，结束查找之后，答案究竟是l-1、r还是mid，mid有三个测试点不过（后来想想也在意料之中），l-1和r都可以，那么怎么判断最后的答案到底是什么呢？因为有check(mid), 这时mid肯定是答案，为了防止弄错，干脆设置一个ans变量。