shunfurh 于 2017.01.10 17:27 提问

River Hopscotch

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

Line 1: Three space-separated integers: L, N, and M
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

Line 1: A single integer that is the maximum of the shortest distance a cow has to jump after removing M rocks
Sample Input

25 5 2
2
14
11
21
17
Sample Output

4

1个回答

caozhy      2017.01.16 23:41

POJ3258：River Hopscotch(二分)
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
【二分法】POJ3258-River Hopscotch
【抱大腿】啊啊啊又是一道恶心的题目！！！这道题是出在二分法里面的，因为这跟前面的一道青蛙过河的题特别像但是不一样，按照青蛙过河那个思路来走根本行不通，正好要按照跟那个思路相反的想法来想才行~ 【题目】 River Hopscotch Time Limit: 2000MS   Memory Limit: 65536K xxxxxxxxx马赛
POJ 3258：River Hopscotch 二分的好想法
River Hopscotch Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 9326   Accepted: 4016 Description Every year the cows hold an event featuring a peculiar ve
【poj 3258】River Hopscotch 题意&题解&代码（C++）
poj 二分
POJ 3258 River Hopscotch （二分经典）
River Hopscotch Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 10591   Accepted: 4543 Description Every year the cows hold an event featuring a peculiar ver
River Hopscotch
http://codevs.cn/problem/3135/ 二分法+DP（可能是） 二分法找出可能是结果的值，循环判断是不是那个值。#include<iostream> #include<stdio.h> #include<cmath> #include<string.h> #include<map> #include<queue> #include<algorithm> using name
usaco 2006 Dec【River Hopscotch跳石头】
Description 奶牛们喜欢参加一种特别的运动——跳石头。它们分别在一条小河的两岸设置了起点和终点，各 放了一块石头，起点和终点间的跨度有 L 米。然后又在河中间放置了 N 块石头，这些石头和起点终 点处于同一条直线上，第 i 块石头距离起点有 Di 米。 游戏的时候，奶牛从起点出发，依次跳过每块石头，最后达到终点。如果两块相邻石头之间的距 离太大，有些奶牛就会跳不过去，掉到河里。约
【poj 3258】River Hopscotch 中文题意＆题解＆代码
River HopscotchTime Limit: 2000MS Memory Limit: 65536K Total Submissions: 10631 Accepted: 4560DescriptionEvery year the cows hold an event featuring a peculiar version of hopscotch that in
1650: [Usaco2006 Dec]River Hopscotch 跳石子
1650: [Usaco2006 Dec]River Hopscotch 跳石子 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 567  Solved: 373 [Submit][Status][Discuss] Description Every year the cows hold an event featuring a pecu
POJ 3258 River Hopscotch（二分）
River Hopscotch Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 8975   Accepted: 3859 Description Every year the cows hold an event featuring a peculiar vers