洛谷P2678跳石头 (二分)
作者:
陈叔健爱学习
,
2022-05-29 15:43:26
,
所有人可见
,
阅读 1535
#include<iostream>
using namespace std;
const int N=50010;
int L,n,m;
int d[N];
bool check(int mid) {
int cnt=0,last=0;//
for(int i=1;i<=n;i++) {
if(d[i] - last < mid) cnt++;//拿走石头
else last=d[i]; // 如果不拿就跳过
}
return cnt<=m;
}
int main()
{
scanf("%d%d%d",&L,&n,&m);
for(int i=1;i<=n;i++) {
scanf("%d",&d[i]);
}
n++;
d[n] = L;//存入终点距离
int l = 1 ,r = 1000000000;
while (l < r) { //二分查找右边界 因为查找的是 最大值
int mid = (l + r + 1) /2;//check()函数的作用是确定答案在mid的左边还是右边
if (check(mid))
l = mid;
else r = mid - 1;
}
printf("%d\n",r);//当r==l时跳出循环,此时找到答案,输出r或l都可以
return 0;
}
呜呜,感觉一变复杂大佬感觉理解不了
厉害厉害