P3853 [TJOI2007]路标设置(二分答案）

二分答案的典型题

注意一下check和输出就行

不知道为啥输出还要再检查一遍

连接：Miku

以下为算法部分

二分

二分部分好说，上我们的二分模板就行了，然后检查一下mid值，如果合法，我们就看一下有没有更小的值

if(check(mid))
r=mid-1;

如果不合法，我们就检查更大值

else
l=mid+1;

check

这部分就是从第一个坐标开始，往后不断检查两点之间的距离，如果距离小于我们的mid，我们就不做处理，反之，我们就在这段空白里加上新的路标，减少他们的距离，并记录增加的数量

（路标放在哪？我经过计算（直觉），只要放在后mid远就肯定行）

最后，检查一下我们增加的数量合不合法就行（我觉得这个check是贪心和枚举把）

————————————

代码

#include<iostream>

using namespace std;

long long l1,n,k;
long long sign[1000100];
bool check(long long f){
    long long last=sign[1];
    long long cnt=0;
    for(long long i=2;i<=n;++i){
        if(sign[i]-last<=f)
        {
            last=sign[i];
        }
        else
        {
            while(sign[i]-last>f){
                last+=f;
                cnt++;
            }
            last=max(sign[i],last);
        }
    }
    if(cnt<=k)
    return 1;
    else
    return 0;
}

int  main()
{
    cin>>l1>>n>>k;
    for(long long i=1;i<=n;++i){
        cin>>sign[i];
        sign[i];
    }    
    long long l=0,r=l1;
    //二分 
    while(l<=r){

        long long mid=l+(r-l)/2;
    //        cout<<l<<" "<<mid<<" "<<r<<endl;
        if(check(mid))
        r=mid-1;
        else
        l=mid+1;

    }//注意，一定要再检查一遍 
    if(check(r))
    cout<<r;
    else
    cout<<l;
    return 0;
}

发送评论编辑评论

二分

check

发送评论 编辑评论

发送评论编辑评论