——————————
二分答案的典型题
——————————
注意一下check和输出就行
——————————
不知道为啥输出还要再检查一遍
——————————
连接：Miku
——————————
以下为算法部分
二分部分好说，上我们的二分模板就行了，然后检查一下mid值，如果合法，我们就看一下有没有更小的值
if(check(mid))
r=mid-1;如果不合法，我们就检查更大值
else
l=mid+1;这部分就是从第一个坐标开始，往后不断检查两点之间的距离，如果距离小于我们的mid，我们就不做处理，反之，我们就在这段空白里加上新的路标，减少他们的距离，并记录增加的数量
（路标放在哪？我经过计算（直觉），只要放在后mid远就肯定行）
最后，检查一下我们增加的数量合不合法就行 （我觉得这个check是贪心和枚举把）
————————————
代码
#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; }
原文：https://www.cnblogs.com/For-Miku/p/11169267.html
