蓝桥杯——路标设置
这可能是我最后一次写二分,我再次尽可能写详细
题目:
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,就去掉了,平时还是要加上特判的。