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

时间:2023-01-01 14:28:51

——————————

二分答案的典型题

——————————

注意一下check和输出就行

——————————

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

——————————

连接:Miku

——————————

以下为算法部分

二分

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

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

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

else
l=mid+1;

check

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

(路标放在哪?我经过计算(直觉),只要放在后mid远就肯定行)

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

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

代码

P3853 [TJOI2007]路标设置(二分答案)P3853 [TJOI2007]路标设置(二分答案)
#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;
} 
AC