首页 > 其他 > 详细

POJ 3258 River Hopscotch (最大最小距离)【二分】

时间:2018-09-22 00:16:03      阅读:164      评论:0      收藏:0      [点我收藏+]

<题目链接>

题目大意:
现在有起点和终点两个石块,这两个石块之间有N个石块,现在对这N个石块移除M个石块,使得这些石块之间的最短距离最大,注意,起点和终点这两个石块不能被移除。

解题分析:

二分答案典型题,二分最大的最短距离,然后根据这个最短距离对这些石块从左向右进行判断,用一个last记录每一次判断的起点,如果当前石块到last的距离<=最短距离,说明该木块需要被移除。对于最后一个石块,由于最后一个石块不能被移除,所以加入最后一个石块到last的距离<=mid,那么就直接移除last即可。

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int  M = 50000+100;
ll arr[M],L,n,m;

bool juge(ll x){
    ll last=0,del=0;
    for(int i=1;i<=n;i++){
        if(arr[i]-last<=x)del++;   //如果当前石块到记录的石块距离<=x,则移除当前石块
        else last=arr[i];
    }
    if(L-last<=x)del++;   //如果last所记录的石块到终点的距离<=x,则移除该记录石块(因为终点的石块不能被移除)
    return del<=m;
}

int main(){
    while(scanf("%lld%d%d",&L,&n,&m)!=EOF){
        for(int i=1;i<=n;i++){
            scanf("%lld",&arr[i]);
        }        
        sort(arr+1,arr+1+n);
        ll l=0,r=L;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(juge(mid))l=mid+1; //由于要最大的最短距离,所以在符合条件的情况下,尽可能的让最短距离更大
            else r=mid-1;
        }
        printf("%lld\n",l);
    }
    return 0;
}

 

 

2018-09-21

POJ 3258 River Hopscotch (最大最小距离)【二分】

原文:https://www.cnblogs.com/00isok/p/9689002.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!