P3853 [TJOI2007] 路标设置——题解

解题思路

二分空旷指数 $d$。对于长度为 gap 的原有间隔，要让所有小间隔不超过 $d$，最少新增路标数为 $\lfloor(gap-1)/d floor$。把所有间隔需求相加，不超过 $K$ 时说明 $d$ 可行，并尝试更小。

复杂度分析

检查 $O(N)$，总时间 $O(N\log L)$，空间 $O(N)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int L,N,K;cin>>L>>N>>K;vector<int>a(N);for(int&i:a)cin>>i;
    auto ok=[&](int d){long long need=0;for(int i=1;i<N;i++)need+=(a[i]-a[i-1]-1)/d;return need<=K;};
    int lo=1,hi=L,ans=L;while(lo<=hi){int mid=(lo+hi)/2;if(ok(mid))ans=mid,hi=mid-1;else lo=mid+1;}
    cout<<ans<<'\n';return 0;
}

#include <bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false);cin.tie(nullptr); int L,N,K;cin>>L>>N>>K;vectora(N);for(int&i:a)cin>>i; auto ok=[&](int d){long long need=0;for(int i=1;i<N;i++)need+=(a[i]-a[i-1]-1)/d;return need<=K;}; int lo=1,hi=L,ans=L;while(lo<=hi){int mid=(lo+hi)/2;if(ok(mid))ans=mid,hi=mid-1;else lo=mid+1;} cout<<ans<<'\n';return 0; }