首页 > 代码库 > HLG 1584 青蛙过河 (二分)
HLG 1584 青蛙过河 (二分)
链接: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1584
Description
青蛙王国一年一度的游戏又开始了,这个游戏要求青蛙必须跳过河。河的宽度是 L 。河里有n块石头,这n块石头从河的一边笔直的连到另一边。青蛙只能踩着石头过河,如果它们掉到水里,将被淘汰出局。游戏规定青蛙最多跳m次。现在青蛙想要知道如果在这m步内跳到岸的那边,它一步最长需要跳多长。
Input
输入包括多组测试结果。
第一行输入三个数字L(1<= L <= 1000 000 000),n(0<= n <= 500000),m(1<= m <= n+1)。
接下来一行有n个用空格隔开的整数,表示每块石头到跳跃起点的距离,两块石头不可能同时出现在一个地方。
Output
对于每次测试,输出一个整数表示青蛙至少应该有的最大的能力,即为一步最多能跳多长,每步实际跳的长度一定小于等于这个最小的最大能力。
Sample Input
6 1 2
2
25 3 3
11 2 18
Sample Output
4
11
代码如下:
#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <algorithm> #define MAXN 500000+10 #define RST(N)memset(N, 0, sizeof(N)) using namespace std; int l, m, n, a[500005]; int jump(int s) { int point = 0, i = 0; int sum = 0; for( ; i<=n; i++) { if(a[i] > point+s) { point=a[i-1]; sum++, i--; } if(sum == m) return 0; } return 1; } int main() { while(~scanf("%d %d %d", &l, &n, &m)) { for(int i=0; i<n; i++) scanf("%d", &a[i]); a[n] = l; sort(a, a+n+1); int left = 1, right = l+1, mid; while(right > left) { mid = (right+left) >> 1; if(jump(mid)) right = mid; else left = mid + 1; } printf("%d\n", right); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。