——————————
二分答案的典型题
——————————
注意一下check和输出就行
——————————
不知道为啥输出还要再检查一遍
——————————
连接:Miku
——————————
以下为算法部分
二分
二分部分好说,上我们的二分模板就行了,然后检查一下mid值,如果合法,我们就看一下有没有更小的值
if(check(mid)) r=mid-1;
如果不合法,我们就检查更大值
else
l=mid+1;
check
这部分就是从第一个坐标开始,往后不断检查两点之间的距离,如果距离小于我们的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; }