当前位置:首页 > 二分 > 正文
NOI1.11-10河中跳房子(NOIP2015跳石头)
3528+

题目大意:n块石头排成一行,你至多可以取走k块,最终相邻两块石头之间的距离最小值最大是多少?

题目描述

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。

输入

第一行包含三个整数L, N, M,相邻两个整数之间用单个空格隔开。
接下来N行,每行一个整数,表示每个岩石与起点的距离。岩石按与起点距离从近到远给出,且不会有两个岩石出现在同一个位置。

输出

一个整数,最长可能的最短跳跃距离。

样例输入

25 5 2
2
11
14
17
21

样例输出

4

提示

NOIP2016提高组第二天第一题

解题思路

题目的答案范围已知,而且范围很大,对于每个答案可以快速验证是否可行,可以采用二分答案的方法。最短距离最大,其实就是越大越好——在二分的时候,如果中间值可行,继续猜后一半,而不是前一半,因为后一半可能有更好的!对于一个答案m,如果可行,那么相邻石头之间的距离都不小于m,也就是如果出现小于m的,那个石头必须移走。写一个函数判断当前答案需要移走多少块石头,如果不超过k块,那就可以,否则不行。

对于二分的结束条件,写法很多种,只要考虑周到就可以。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,,

NOI1.11-10河中跳房子(NOIP2015跳石头):等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter