第十四届蓝桥杯省赛pythonB组题。 管道
5407. 管道 - AcWing题库
有一根长度为 len的横向的管道,该管道按照单位长度分为 len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。
一开始管道是空的,位于 Li 的阀门会在 Si 时刻打开,并不断让水流入管道。
对于位于 Li的阀门,它流入的水在 Ti(Ti≥Si)时刻会使得从第 Li−(Ti−Si) 段到第 Li+(Ti−Si) 段的传感器检测到水流。
求管道中每一段中间的传感器都检测到有水流的最早时间。
输入格式
输入的第一行包含两个整数 n,len,用一个空格分隔,分别表示会打开的阀门数和管道长度。
接下来 n 行每行包含两个整数 Li,Si用一个空格分隔,表示位于第 Li 段管道中央的阀门会在 Si 时刻打开。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30%30% 的评测用例,n≤200,Si,len≤3000;
对于 70%70% 的评测用例,n≤5000,Si,len≤105;
对于所有评测用例,1≤n≤105,1≤Si,len≤109输入样例:
3 10 1 1 6 5 10 2
输出样例:
5
我个人认为非常经典的二分+区间合并题目,一定要好好理解这道题。
根据题目,水流会慢慢向两边增加,求满足题目要求的时刻 t ,就容易发现 t 具有单调性,因为 t 越大,水流流通的范围就越大,就可以通过二分找到临界点 t ,每次二次 t 的时候,相当于 t 确定,然后遍历阀门,可以判断 t 时刻此阀门是否开启,未开启则跳过,否则把该阀门水流的范围 left 和 right 记录下来,然后就是典型的区间合并问题,判断是否覆盖1-len的区间。
根据题目,二分过程中可能会爆int ,需要开 long long , 且二分范围,左端点显然是1,右端点需要2*len,也就是2e9,因为存在len为1e9时,最后时刻才打开最左边或最右边阀门的最坏情况
AC code:
#include <bits/stdc++.h> using namespace std; struct s {int l, s; } arr[100010];int n, len; int check(int mid) {int cnt = 0;pair<int, int> q[100010];for (int i = 1; i <= n; i++) {if (arr[i].s > mid) continue;int t = mid - arr[i].s;int l = max(1, arr[i].l - t), r = min((long long)len, (long long) arr[i].l + t);q[cnt++] = {l, r};}sort(q, q + cnt); // int be = -1, en = -1; // for (int i = 0; i < cnt; i++) { // if (q[i].first <= en + 1) { // en = max(en, q[i].second); // } else { // be = q[i].first, en = q[i].second; // } // } // return be==1&&en==len; // if(q[0].first>0) return 0; // if(q[cnt-1].second<len) return 0;int en = q[0].second;if(q[0].first!=1) return 0;for (int i = 1; i < cnt; i++) {if (q[i].first > en + 1) {return 0;} en=max(en,q[i].second);}return en>=len; } int main() {cin >> n >> len;for (int i = 1; i <= n; i++) {cin >> arr[i].l >> arr[i].s;}int l = 0, r = 2e9 + 10;while (l < r) {int mid = (long long)l + r >> 1 ;if (check(mid)) r = mid;else l = mid + 1;}cout << l << endl;return 0; }
相关文章:
第十四届蓝桥杯省赛pythonB组题。 管道
5407. 管道 - AcWing题库 有一根长度为 len的横向的管道,该管道按照单位长度分为 len 段,每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的,位于 Li 的阀门会在 Si 时刻打开,并不断让水流入管道。…...

淘宝扭蛋机小程序:新时代的互动营销与娱乐体验
随着科技的快速发展,小程序已经成为人们日常生活中不可或缺的一部分。在众多的小程序中,淘宝扭蛋机小程序以其独特的互动性和趣味性,吸引了大量用户。本文将深入探讨淘宝扭蛋机小程序的特色、用户体验以及未来发展。 一、淘宝扭蛋机小程序的…...

深度强化学习(王树森)笔记02
深度强化学习(DRL) 本文是学习笔记,如有侵权,请联系删除。本文在ChatGPT辅助下完成。 参考链接 Deep Reinforcement Learning官方链接:https://github.com/wangshusen/DRL 源代码链接:https://github.c…...

【分布式技术专题】「分布式技术架构」 探索Tomcat技术架构设计模式的奥秘(Server和Service组件原理分析)
探索Tomcat技术架构设计模式的奥秘 Tomcat系统架构分析Tomcat 整体结构Tomcat总体结构图以 Service 作为“婚姻”1) Service 接口方法列表 2) StandardService 的类结构图方法列表 3) StandardService. SetContainer4) StandardService. addConnector 以 Server 为“居”1) Ser…...
常用的gpt-4 prompt words收集8
本文介绍我最近收集的一些好用的chatgpt-4的prompts,如果你也有好用的提示词可以互相交流一下。 1. I ran into some trouble on my way to work. 迟到原因 2. In my heart, the most delicious coffee is the Hawaii Dirty from Manner. Only the Nong series a…...

【GitHub项目推荐--开源2D 游戏引擎】【转载】
microStudio 是一个可在浏览器中运行的游戏引擎,它拥有一套精美、设计精良、全面的工具,可以非常轻松地帮助你创建 2D 游戏。 你可以在浏览器中访问 microStudio.dev 开始搭建你的游戏,当然你可以克隆现有项目或创建新游戏并开始编码&#x…...

鸿蒙APP的应用场景
鸿蒙APP可以用于多种场合和设备类型,这是鸿蒙系统的分布式能力和多终端适配的优势。以下是一些鸿蒙APP的应用场景,希望对大家有所帮助。北京木奇移动技术有限公司,专业的软件外包开发公司,欢迎交流合作。 1.智能手机和平板电脑&am…...

goland课程管理(6)
项目目录结构如下图所示: core包下面: class.go package coreimport "github.com/gin-gonic/gin"func Class1(ctx *gin.Context) {}course.go package coreimport (. "cookie/database". "cookie/model""fmt"…...
04.Elasticsearch应用(四)
Elasticsearch应用(四) 1.什么是索引 索引是文档的容器,是一类文档的结合索引是一个逻辑命名空间,它映射到一个或多个主分片,并且可以具有零个或多个副本分片索引中数据分散在Shard上索引的Mapping定义文档字段的类型…...

Python之数据可视化(地图)
目录 一 基础地图应用 二 全国疫情图 一 数据准备 二 数据处理 二 湖北省疫情图 一 数据准备 二 数据处理 一 基础地图应用 导入map地图对象 from pyecharts.charts import Map map Map() 写入数据 data [("北京市",100),("上海市"…...

etcd技术解析:构建高可用分布式系统的利器
1. 引言 随着云原生技术的兴起,分布式系统的构建变得愈发重要。etcd作为一个高可用的分布式键值存储系统,在这个领域发挥着至关重要的作用。本文将深入探讨etcd的技术细节,以及如何利用它构建高可用的分布式系统。 2. etcd简介 etcd是一个开…...
Pillow图像处理:从零开始的奇妙之旅
图像处理,就像是一场神奇的冒险,让我们的照片变得更有趣、更生动。而在这个冒险的旅途中,Pillow就如同一位魔法师,为我们开启了无尽的可能性。无论你是刚刚踏入图像处理领域的小白,还是已经略有基础的程序员࿰…...
设计一个LRU(最近最少使用)缓存
约束和假设 我们正在缓存什么? 我们正在缓存Web Query的结果我们可以假设输入是有效的,还是需要对其验证? 假设输入是有效的我们可以假设它适应内存吗? 对 编码实现 class Node(object):def __init__(self, results):self.res…...
shell 循环语句
一、命令补充 1. echo 命令 echo -n 表示不换行输出 echo -e 表示输出转义符 常用的转义符有: 选项作用\r光标移至行首,并且不换行\s当前shell的名称,如bash\t插入Tab键,制表符\n输出换行\f换行,但光标仍停留在…...
C++(1) 命名空间
文章目录 C1. C 概述2.C 相对于 C 语言的增强2.1C 第一行代码2.2 C 补充 bool 类型2.3 作用域运算符2.4 命名空间 namespace2.4.1 命名空间基本内容和开放性2.4.2 多个命名空间操作2.4.3 命名空间函数定义和实现分离2.4.4 匿名命名空间2.4.5 命名空间别名 C 1. C 概述 C 之父…...

【机组】单元模块实验的综合调试与驻机键盘和液晶显示器的使用方式
🌈个人主页:Sarapines Programmer🔥 系列专栏:《机组 | 模块单元实验》⏰诗赋清音:云生高巅梦远游, 星光点缀碧海愁。 山川深邃情难晤, 剑气凌云志自修。 目录 1. 综合实验的调试 1.1 实验…...
React中实现虚拟加载滚动
前言:当一个页面中需要接受接口返回的全部数据进行页面渲染时间,如果数据量比较庞大,前端在渲染dom的过程中需要花费时间,造成页面经常出现卡顿现象。 需求:通过虚拟加载,优化页面渲染速度 缺点:…...

vue中的Mutations
目录 一:介绍 二:例子 一:介绍 Vuex 中的 mutation 非常类似于事件: 每个 mutation 都有一个字符串的 事件类型 (type) 和 一个 回调函数 (handler)。这个回调函数就是我们实际进行状态更改的函数,并且它会接受 sta…...

C#用 DateAndTime.DateAdd方法和DateTime.Add(TimeSpan) 方法分别添加一段时间间隔
目录 一、基本方法 1.用 DateAndTime.DateAdd方法添加一段时间间隔 2.用DateTime.Add方法添加一段时间间隔 二、实例 1.实例1:用 DateAndTime.DateAdd方法 2.实例2:用DateTime.Add方法 一、基本方法 1.用 DateAndTime.DateAdd方法添加一段时间间隔…...

四、Kotlin 表达式
1. 常量 & 变量 1.1 可读写变量(var) var x initValue // x 称为可读写变量注意:当 var 声明的变量做成员属性时,默认提供 setter/getter 方法。 1.2 只读变量(val) val x initValue // x 称为只…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...

MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...

【C++】纯虚函数类外可以写实现吗?
1. 答案 先说答案,可以。 2.代码测试 .h头文件 #include <iostream> #include <string>// 抽象基类 class AbstractBase { public:AbstractBase() default;virtual ~AbstractBase() default; // 默认析构函数public:virtual int PureVirtualFunct…...

Unity中的transform.up
2025年6月8日,周日下午 在Unity中,transform.up是Transform组件的一个属性,表示游戏对象在世界空间中的“上”方向(Y轴正方向),且会随对象旋转动态变化。以下是关键点解析: 基本定义 transfor…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合
作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...
上位机开发过程中的设计模式体会(1):工厂方法模式、单例模式和生成器模式
简介 在我的 QT/C 开发工作中,合理运用设计模式极大地提高了代码的可维护性和可扩展性。本文将分享我在实际项目中应用的三种创造型模式:工厂方法模式、单例模式和生成器模式。 1. 工厂模式 (Factory Pattern) 应用场景 在我的 QT 项目中曾经有一个需…...
小木的算法日记-多叉树的递归/层序遍历
🌲 从二叉树到森林:一文彻底搞懂多叉树遍历的艺术 🚀 引言 你好,未来的算法大神! 在数据结构的世界里,“树”无疑是最核心、最迷人的概念之一。我们中的大多数人都是从 二叉树 开始入门的,它…...