【例1】跳石头。
题目描述
一年一度的“跳石头”比赛又要开始了!
这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。
为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 MM 块岩石(不能移走起点和终点的岩石)。
输入输出格式
输入格式:
第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。。
接下来 N 行,每行一个整数,第 i 行的整数 D_i( 0 < D_i < L), 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。
输出格式:
一个整数,即最短跳跃距离的最大值。
输入输出样例
输入样例#1:
25 5 2
2
11
14
17
21
输出样例#1:
4
说明
输入输出样例 1 说明:将与起点距离为 2和 14的两个岩石移走后,最短的跳跃距离为 4(从与起点距离 17的岩石跳到距离 21的岩石,或者从距离 21的岩石跳到终点。
(1)编程思路。
这道题要求一堆最小距离里面的最大值,是一道典型的最小值最大化问题,可以采用二分法解决。
1)首先将距离排序,虽然石子顺序是确定的,但是排完序不影响它们之间的差值,这个是肯定的。
2)确立二分的上下界,上界right就是河流的宽度L,下界left就是最小石头间距。
3)然后在上下界之间二分,二分时需要确定判断条件,测试当前的mid值。
判断当前mid值的方法是这样的:循环所有的石头间距,逐个累加,如果没有超过当前mid,意味着该石头可以搬开(这是为了保证最小跳跃长度为mid,小于mid距离的石头不能往上面跳,因为如果一跳就会出现比mid更小的距离了),即搬石头数x++,如果超过了当前mid,则不能搬了(需要跳到这个石头上落下脚),而且要把此时的累加距清零,以便后一段继续如此处理。
根据循环之后的结果,如果搬石头数目x超过了规定的m,说明mid值过大,于是上界缩小right变为mid-1:如果x小于m,则在跳跃时还可以跳过m-x个石头,说明mid值偏小,则下界增大left变为mid+1……由此二分完毕即得最大化最小间距。
(2)源程序。
#include <iostream>
#include <algorithm>
using namespace std;
int d[50005],l,n,m;
bool judge(int mid)
{
int start=0,x=0,i; // start表示每次落脚点的坐标,每落一次地更新一次start
for(i=1;i<=n;i++)
{
if (d[i]-start<mid)
x++; // x表示去掉的石头数,如果mid大于要跳的距离,就跳过当前这个石头,此时x++
else
start=d[i]; // 此时落在石头上
}
if (l-start<mid) // 判断最后一跳跳的距离要是小于mid的话那是不可以的
return false;
if(x>m) // 要是x>m就说明最小距离mid太大啦
return false;
return true;
}
int main()
{
int left,right,mid,ans,min = 0x7fff,i;
cin>>l>>n>>m;
for(i=1;i<=n;i++)
cin>>d[i];
d[0] = 0;
d[n + 1] = l;
sort(d,d+(n+1));
for(i = 0; i <= n; i++)
i