- POJ 3258 - River Hopscotch
- Time: 2000MS
- Memory: 65536K
- 难度: 初级
- 分类: 二分法
0x00 POJ 原题
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 D_(i) from the start (0 < D_(i) < 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
17Sample Output
4Hint
Before removing any rocks, the shortest jump was a jump of 2 from 0 (the start) to 2. After removing the rocks at 2 and 14, the shortest required jump is a jump of 4 (from 17 to 21 or from 21 to 25).
Source
0x10 题目概述
一条河长度为 L，河的起点(Start)和终点(End)分别有 2 块石头，S 到 E 的距离就是 L。
河中有 n 块石头，每块石头到 S 都有唯一的距离
问现在要移除 m 块石头（S 和 E 除外），每次移除的是与当前最短距离相关联的石头，要求移除 m 块石头后，使得那时的最短距离尽可能大，输出那个最短距离。
0x20 解题思路
经典的二分，理解题意就不怎么难了 （其实编程不难，要理解就非常难。。。。）
详细的解释看我的程序，实在看不懂就参考一下我 POJ3273 的做法，看上去不同，其实思路是差不多的，数学题都很难理解的，耐心吧。。。。
我感觉说了好像没说的感觉， 总之看程序吧
0x30 AC 源码
//Memory Time
//420K 391MS
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
int L; //河总长
int n; //河中石头数（除起点S和终点外E）
int m; //移除石头数
while(cin>>L>>n>>m)
{
/*Input & Initial*/
int* dist=new int[n+2]; //第i块石头到起点石头的距离为dist[i]
dist[0]=0; //起点S
dist[n+1]=L; //终点E
int low=L; //上界(一次跳跃的最短距离)
int high=L; //下界(一次跳跃的最大距离)
for(int i=1;i<=n+1;i++)
{
if(i<=n) //仅输入1~n，当i=n+1时仅用于寻找low
cin>>dist[i];
if(low > dist[i]-dist[i-1])
low=dist[i]-dist[i-1];
}
sort(dist,dist+(n+2)); //根据石头到S的距离升序排列
/*Binary-Search*/
while(low<=high)
{
int mid=(low+high)/2; //对最大跳和最小跳的距离折中，二分查找mid相对于最优解是偏大还是偏小
//假设mid是移除m个石头后的最短距离
int delrock=0; //利用当前的mid值能移除的石头数
int sum=0; //类比POJ 3273, 这里是 连续距离的累加值
//当在第i个距离累加后sum
for(int i=1;i<=n+1;)
{
if( (sum+=dist[i]-dist[i-1]) <= mid)
{
i++;
delrock++;
}
else //当从第i个距离累加到i+k个距离后，若sum>mid，则k个距离作为一段
{
i++;
sum=0; //sum置0，从第i+k+1个距离重新累加
}
}
if(delrock<=m) //本题难点之一：即使delrock==m也不一定找到了最优解
low=mid+1; //用当前mid值移除的石头数小于规定数，说明mid偏小
else
high=mid-1; //反之mid偏大
}
/*Output & Relax*/
cout<<low<<endl;
delete dist;
}
return 0;
}
