题解 P3853 【[TJOI2007]路标设置】

· · 题解

这是道巨大的二分答案题 这道题呢，我用的算法是二分+贪心+枚举 好了，下面来讲一下思路

二分

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

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

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

else
l=mid+1;
check

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

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

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

AC

下面就是代码了

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