第十四届蓝桥杯省赛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 称为只…...

docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
连锁超市冷库节能解决方案:如何实现超市降本增效
在连锁超市冷库运营中,高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术,实现年省电费15%-60%,且不改动原有装备、安装快捷、…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...

算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...

C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...

MLP实战二:MLP 实现图像数字多分类
任务 实战(二):MLP 实现图像多分类 基于 mnist 数据集,建立 mlp 模型,实现 0-9 数字的十分类 task: 1、实现 mnist 数据载入,可视化图形数字; 2、完成数据预处理:图像数据维度转换与…...