蓝桥杯——路标设置

这可能是我最后一次写二分，我再次尽可能写详细

题目：

tim

题目给出了个定义：空旷指数（在整个路程中，两个相邻路灯的最大距离）

通过题意可知，我们要的是在给出可设置路灯数目的限制下，得到一个最小空旷指数 

因此，我们可以明白这是一道求最大值最小问题

 对于一个二分问题，我们应该解决如下问题

1.数组是否按序排列                  显然是按序

2.我们要二分求得的哪一个值                空旷指数（路灯的最大距离）

3.空旷指数的取值范围                   最大可以为L（路长）因为中间可以不放路灯，就结尾和开头各一个路灯，最小可以为1，即相邻位置都放一个路灯，因此定义时l=0，r=L+1。

4.bool函数判断条件                        操作数op要小于等于可放置路灯数目

5.二分结果左右时bool通过的区域       

可以试想如果最大距离越大，op放的路灯就会越少，那么就更应该通过bool测试，因此左错右对

事实上如果最大值最小问题，都是这样的情形 

6.边界移动问题        这个问题我觉得解释上非常困难，但是通过画图就十分明显

答案

测试点信息源代码
源代码 复制
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int L,n,K;
int q[N],s[N];

bool check(int x)
{
	int op = 0;
	for(int i = 1;i<=n;i++){
		if(s[i]>x){
			op+=(s[i] - 1)/x;
			
		}
	}
	if(op>K) return false;
	else return true;
}

int main() {
	cin >> L >> n >> K;
	q[0]=0;
	for(int i = 1;i <= n; i++) {
		cin >> q[i];
		s[i] = q[i] - q[i-1];
	}
	
	int l = 0,r = L+1;
	while(l+1<r)
	{
		int mid = (l + r) / 2;
		if(check(mid)) r=mid;
		else l = mid;
	}
	
	
	cout << r;
	return 0;
}

加一个特判的话，会报RE错误。原理我也不太了解，但是没关系，加了特判测试点还是全对，所以无所谓，这里为了AC，就去掉了，平时还是要加上特判的。