The Frog's Games
Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 133Accepted Submission(s): 70
Problem Description
The annual Games in frogs' kingdom started again. The most famous game is the Ironfrog Triathlon. One test in the Ironfrog Triathlon is jumping. This project requires the frog athletes to jump over the river. The width of the river
is L (1<= L <= 1000000000). There are n (0<= n <= 500000) stones lined up in a straight line from one side to the other side of the river. The frogs can only jump through the river, but they can land on the stones. If they fall into the river, they
are out. The frogs was asked to jump at most m (1<= m <= n+1) times. Now the frogs want to know if they want to jump across the river, at least what ability should they have. (That is the frog's longest jump distance).
Input
The input contains several cases. The first line of each case contains three positive integer L, n, and m.
Then n lines follow. Each stands for the distance from the starting banks to the nth stone, two stone appear in one place is impossible.
Output
For each case, output a integer standing for the frog's ability at least they should have.
Sample Input
Sample Output
Source
这个题因为要求最小的最大
很明显应该用二分答案的方法。
关键是判断部分,如果直接暴力判断是二重循环。
这里可以用upper_bound函数把复杂度降下来。
二分+贪心判定
我的代码:
分享到:
相关推荐
收集的部分HDOJ杭电ACM题的代码 大牛勿下 全是基础供初级acmer使用
自己积累的部分杭电oj的(hdu)解题代码。。大家有空来看看。 基本上是自己写的哈。有错误之处请指教、
HDOJ,2011阿里巴巴程序设计公开赛的标程 题目位置:http://acm.hdu.edu.cn/vip/2011alibaba/index.php
杭电oj4405,一道简单的概率dp题目
ACM ICPC HDOJ1000
杭电acm解题报告 详细解析2000-2099 适合acm初学者
思路:这个题和HDU - 5703类似,其实就是拆数问题,一个数的拆法其实就是2^(N-1),具体证明过程可以直接搜刚才杭电那道题的题解,所以这道题其实就是让你算2^(N-1),但是题目给的N特别大, 可以达到10^100000,我们...
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
离线OJ题库(HDU ZJU等,部分有答案),需联网。
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
杭州电子科技大学hdoj1002,大整数相加问题
HDU的一题........HDU DP动态规
HDU ACM 2005第几天 C++ http://acm.hdu.edu.cn/listproblem.php?vol=11 2005题 第几天?
hdu 期末考试复习资料 计算机网络 编译原理 计算机图形学 编译原理 信息安全与技术 数据库应用系统开发
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
ACM HDU题目分类,我自己总结的大概只有十来个吧
本人杭电上题目java实现的代码,绝无其他无用的内容,知道的都晓得这是什么
ACM ICPC HDOJ 1005
杭电ACMhdu1163
HDU1059的代码