自动搬运

查看原文

来自洛谷，原作者为

	DarkShadow 成功只有一个——按照自己的方式，去度过人生

搬运于2025-08-24 23:02:26，当前版本为作者最后更新于2024-08-28 13:10:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10909（二分）

思路分析：

首先观察到本题答案具有单调性，于是我们可以考虑二分最远距离 $L$。

然后考虑如何检查答案，对于原有的这些检查点，每两个检查点之间需要 $\lceil \frac{dis}{L} \rceil-1$ 个新增检查点，其中 $dis$ 表示两个检查点之间的距离，然后判断总检查点个数是否小于 $m$ 就可以了。

那么爆发技能我们该怎么处理呢？由于使用技能可以使距离变成原来的两倍，其实就相当于新增了一个检查点，所以只用给 $m$ 加一就可以了。

完整代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,d[N];
bool check(int a){//检查是否合法
	int cnt=0;
	for(int i=1;i<=n;i++)
		cnt+=int(double(d[i]-d[i-1])/double(a)+0.999999)-1;
	return cnt<=m+1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&d[i]);
	int l=1,r=d[n],mid;
	while(l<r){//二分答案
		mid=l+r>>1;
		if(check(mid))  r=mid;
		else  l=mid+1;
	}
	printf("%d",l);
	return 0;
}