POJ3258 River Hopscotch —— 二分
题目链接:http://poj.org/problem?id=3258
Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 15753 | Accepted: 6649 |
Description
Every year the cows hold an event featuring a peculiar version of hopscotch that involves carefully jumping from rock to rock in a river. The excitement takes place on a long, straight river with a rock at the start and another rock at the end, L units away from the start (1 ≤ L ≤ 1,000,000,000). Along the river between the starting and ending rocks, N (0 ≤ N ≤ 50,000) more rocks appear, each at an integral distance Di from the start (0 < Di < L).
To play the game, each cow in turn starts at the starting rock and tries to reach the finish at the ending rock, jumping only from rock to rock. Of course, less agile cows never make it to the final rock, ending up instead in the river.
Farmer John is proud of his cows and watches this event each year. But as time goes by, he tires of watching the timid cows of the other farmers limp across the short distances between rocks placed too closely together. He plans to remove several rocks in order to increase the shortest distance a cow will have to jump to reach the end. He knows he cannot remove the starting and ending rocks, but he calculates that he has enough resources to remove up to M rocks (0 ≤ M ≤ N).
FJ wants to know exactly how much he can increase the shortest distance *before* he starts removing the rocks. Help Farmer John determine the greatest possible shortest distance a cow has to jump after removing the optimal set of M rocks.
Input
Lines 2..N+1: Each line contains a single integer indicating how far some rock is away from the starting rock. No two rocks share the same position.
Output
Sample Input
25 5 2
2
14
11
21
17
Sample Output
4
Hint
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5; int L, N, M;
int a[MAXN]; bool test(int mid)
{
int cnt = , pre = ;
for(int i = ; i<=N; i++)
{
if(a[i]-a[pre]<mid) cnt++;
else pre = i;
}
return cnt<=M;
} int main()
{
while(scanf("%d%d%d",&L, &N, &M)!=EOF)
{
for(int i = ; i<=N; i++)
scanf("%d",&a[i]); a[++N] = ; a[++N] = L;
sort(a+, a++N); int l = , r = L;
while(l<=r)
{
int mid = (l+r)>>;
if(test(mid))
l = mid + ;
else
r = mid - ;
printf("%d %d\n", l, r);
}
printf("%d\n", r);
}
}
最新文章
- JAVA hashmap知识整理
- 【1】第一次电话面试---上海EMC
- JSPatch中的OC高级语法
- java 15-2 Collection的高级功能测试
- C#相对路径转绝对路径,绝对路径转相对路径
- sql工作问题总结
- C#之 HashSet(临时笔记,未参考资料,请慎重)
- C#程序中:如何向xml文件中插入节点(数据)
- Cocos2d-x3.0 捕Android菜单键和返回键
- JSP与ASP.PHP的比較
- 深入浅出docker
- linux设置oracle自动启动
- CVS简介
- Java内存溢出异常(下)
- python二叉树练习
- bzoj1830 Y形项链
- Android 命令行打包和签名
- python-pymongo使用
- drupal7 自定义登录&;找回密码页面,注意事项
- BZOJ1912 APIO2010 洛谷P3629 巡逻
热门文章
- 浅谈java内存泄漏
- Spring-IOC源码解读2.3-BeanDefinition的注册
- mongodb的安装及环境配置
- Win10下安装虚拟机提示“Intel VT-x处于禁用状态”如何解决
- 洛谷 [P3480] KAM-Pebbles
- HTML 文档之 Head 最佳实践--摘抄
- css-包含块
- Lucene 6.5.0 入门Demo
- 【Android】状态栏通知Notification、NotificationManager详解(转)
- 解决三星 BIOS 模式没有 Fast Bios Mode选项 U盘动项问题