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

· · 题解

此题为二分求最优解的模板

对于任意一个给出的“空旷指数”G，我们应该怎样去判断它是否符合题目的意思呢？

我们可以想象，我们已知了这条路上的所有的路标，我们从头开始枚举两两相邻的路标的间距，如果大于G,那么已经不符合G为最大距离的条件了，为了使G满足,我们就可以在前一个路标前面G米处加一个路标，这样与前面一个就符合条件了，再判断新设的路标和后面的路标是否距离小于G,如果不，继续重复操作设置新路标

当新设的路标数已经超过题目所给最大增设值时，如果还有路标不满足G,但已经不能设置新路标了，所以该G值就不满足条件。相反，则G成立。

注意到，如果一个“空旷指数”成立，那么可能存在比它更小的解，但如果一个“空旷指数”不成立，那么答案只能比该值更大

确定了判断方法，我们就可以写二分的代码了：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int sit[100005];
int L,N,K;
inline bool check(int m)
{
    int y=K;
    int size=0;//确定当前的比较位置
    for(int i=1;i<N;i++)
    {
        if(y<0)
        {
            break;
        }
        if(sit[i]-size<=m)
        {
            size=sit[i];//成立则移动比较位置，比较下一组
        }
        else
        {
            size=size+m;//设置新的路标，前一个路标已满足，移动位置到新路标
            i--;//防止因为循环把之前的路标给移走了！
            y--;//减少可用新路标数
        }
    }
    if(y>=0)
    {
        return true;
    }
    return false;
}
int main()
{
    cin>>L>>N>>K;
    int t=0;
    while(t<N)
    {
        cin>>sit[t];
        t++;
    }
    int H=0,R=L;
    int ans;
    while(H<=R)
    {
        int mid=H+(R-H)/2;
        if(check(mid))
        {
            ans=mid;//记录
            R=mid-1;//可能存在更小的“空旷指数”，搜索左区间
        }
        else
        {
            H=mid+1;//答案只能是更大的“空旷指数”，搜索右区间
        }
    }
    cout<<ans;
}