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

蓝桥杯——路标设置

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

题目:

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,就去掉了,平时还是要加上特判的。


http://www.kler.cn/a/586348.html

相关文章:

  • Celery - 入门(get-started)
  • 精准车型识别:视觉分析技术的力量
  • 海鲜水产行业wordpress外贸主题
  • Golang Channel 使用详解、注意事项与死锁分析
  • 软考教材重点内容 信息安全工程师 第19章 操作系统安全保护
  • Dify1.01版本vscode 本地环境搭建运行实践
  • AI+Python机器学习小项目教程(数据分类)
  • 算法基础 -- Brian Kernighan 算法初识
  • 基础知识《HTTP字段与状态码详细说明》
  • 【基于 SSE 协议与 EventSource 实现 AI 对话的流式交互】
  • Stable Diffusion API /sdapi/v1/txt2img的完整参数列表及其说明
  • leetcode hot 100(三)
  • python全栈-MySQL知识
  • MySQL:MySQL库和表的基本操作
  • SpringBoot实现一个Redis限流注解
  • Springboot项目修改端口
  • 深入理解Spring Boot:快速构建现代化的Java应用
  • 【调研】模型输出内容的json形式content怎样处理可以转换为json?
  • kafka生成者发送消息失败报错:RecordTooLargeException
  • MCU的工作原理:嵌入式系统的控制核心