POJ 3258 - River Hopscotch


问题描述

一条河长度为 L,河的起点(Start)和终点(End)分别有2块石头,S到E的距离就是L。

河中有n块石头,每块石头到S都有唯一的距离

问现在要移除m块石头(S和E除外),每次移除的是与当前最短距离相关联的石头,要求移除m块石头后,使得那时的最短距离尽可能大,输出那个最短距离。

解题思路

经典的二分,理解题意就不怎么难了 (其实编程不难,要理解就非常难。。。。)

详细的解释看我的程序,实在看不懂就参考一下我 [POJ3273](.//Memory Time
//420K 391MS

#include
#include
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;

}


------


## 相关资料

- [北大 ACM - POJ 试题分类](https://exp-blog.com/algorithm/poj-shi-ti-fen-lei/)
- [北大 POJ 题库(官网在线)](http://poj.org/)
- [北大 POJ 题库(离线版)](https://github.com/lyy289065406/POJ-Solving-Reports/doc/POJ%E7%A6%BB%E7%BA%BF%E7%89%88%E9%A2%98%E7%9B%AE.chm)
- [POJ封面书《程序设计导引及在线实践》](https://github.com/lyy289065406/POJ-Solving-Reports/doc/程序设计导引及在线实践.pdf)
- [ACM 资料](https://lyy289065406.github.io/articles/tags/ACM/)

文章作者: EXP
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 EXP !
 上一篇
POJ 1159 - Palindrome POJ 1159 - Palindrome
POJ 1159 - Palindrome Time: 3000MS Memory: 65536K 难度: 初级 分类: 动态规划 问题描述无。 解题思路设 原序列S的逆序列为S’,则这道题目的关键在于: 最少需要补充的字母数 = 原序
2011-11-02
下一篇 
POJ 3094 - Quicksum POJ 3094 - Quicksum
POJ 3094 - Quicksum Time: 1000MS Memory: 10000K 难度: 水题 分类: 无 问题描述无。 解题思路见代码注释。 AC 源码 Download Link /* Author:
2011-10-25
  目录