AcWing 519. 跳石头(二分)(边界条件什么巧妙特判)
原题链接
中等
作者:
逸误
,
2024-03-25 21:15:05
,
所有人可见
,
阅读 7
//不要陷入死胡同!考虑面向答案的二分!
//要找到最大的mindist,就用check函数二分,如果dist小于目前列举的mindist就一定要拿走那块石头
//求最短的xx,最大的xx,多考虑二分可不可以做
//二分多考虑边界条件!第一次写的时候忘记了最后一段
//这里用了巧妙的特判,把终点看成第n+1块石头,byd我是没想到
#include <iostream>
using namespace std;
const int N = 50005;
int l,n,m;
int a[N];
bool check(int t)//t是mindist
{
int last=0;
int sum=0;//现在已经取走多少石头了
for(int i=1;i<=n+1;i++)
{
if(a[i]-last<t)//需要拿走第i块,不更新last
{
sum++;
if(sum>m)
return false;
continue;
}
else
{
last=a[i];
}
}
return true;
}
int main()
{
cin>>l>>n>>m;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
a[n+1]=l;//byd,边界条件还可以这样特判的,如果最后到终点的路过短,其实只需要多移走终点上一步的石头就保证达成了,所以将终点也视为一块石子,距离过短时“移走”
int l=0,r=1e9;
while(l<r)
{
int mid=l+r+1>>1;
if(check(mid))
l=mid;
else
r=mid-1;
}
cout<<l<<endl;
return 0;
}