当前位置：首页 > article >正文

蓝桥杯——路标设置

article 2025/3/16 2:34:02

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

题目：

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;
}