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

MarkMHY · 2019-04-09 15:51:58 · 题解

L、N、K，分别表示公路的长度，原有路标的数量，以及最多可增设的路标数量。 用二分去寻找最小的“空旷指数”。 C++代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxN=100001;
int x[maxN];
int L,N,K;
bool judge(int d)
{
    int cnt=0,last=0;
    int i=1;
    while(i<=N)
    {
        if(x[i]-last<=d)
        {
            last=x[i];
            i++;
        }
        else
        {
            cnt++;
            last+=d;
            if(cnt>K)
            {
                return false;
            }
        }
    }
    if(last<L)
    {
        return false;
    }
    else
    {
        return true;
    }
}
int main()
{
    int left,right,mid;
    cin>>L>>N>>K;
    for(int i=1;i<=N;i++)
    {
        cin>>x[i];
    }
    left=1;
    right=x[N];
    while(left<=right)
    {
        mid=(left+right)/2;
        if(!judge(mid))
        {
            left=mid+1;
        }
        else
        {
            right=mid-1;
        }
    }
    cout<<left<<endl;
    return 0;
}