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

set 和 map 的左右护卫 【刷题反思】

1. 相近的营业额

1.1 题目

题目描述:我们定义,一天营业额的最小波动 = min { | 该天以前某一天的营业额 - 该天营业额 | }

                  特别的,第一天的营业额最小波动为第一天的营业额

输入描述:第一行 n (n <= 32767),表示公司从成立到现在的天数

                  接下来 n 行每行有一个整数 ai (|ai| <= 10e6),表示第 i 天的营业额,可能存在负数

输出描述:一个正整数,表示每一天最小波动的和,保证结果小于 2^31

输入:

6

5

1

2

5

4

6

输出:

12

1.2 思想

对于每一个新的数 x ,我们总共要找到距离 x 最近的一大一小的两个数,可以将之前的数据放入到 set 中,对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器,让迭代器进行(--)操作,可以得到比 x 小的最接近 x 的值,然后让各自与 x 的差值进行比较就可以得到最小波动值

值得注意的是:当对迭代器进行(--)操作时,如果 set 里的元素不够,可能非法访问,所以我们需要左右护法进行保护,而左右护法也不能干涉比较的结果,那左右护法可以趋于无穷(即这个情况下不可能取到的值)

1.3 模拟实现

#include<iostream>
using namespace std;
#include<set>
#include<cmath>
set<int> mp;
//注意近似无穷的值
int INF = 1e7+10;
int total;
int main()
{int n; cin >> n;int x; cin >> x;//先将第一天的值插入mp.insert(x);total += x;//添加左右护法mp.insert(INF);mp.insert(-INF);for(int i=2;i<=n;i++){int x; cin >> x;//取出大于等于 x 的值的迭代器auto it1 = mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 = it1;it2--;//进行比较total += min(abs( *it1 - x ), abs( *it2 - x ));//最后将今天的 x 插入mp.insert(x);}cout << total << endl;return 0;
}

2. 相近的木材

2.1 题目

题目描述:有一个木材仓库,里面没有两个木材的长度相同,现在有不超过100000条操作:

                  进货格式:1 length:向仓库中放入长度为 length (不超过 10e9)的木材,如果已经存在,就输出 Already Exist

                  出货格式:2 length:仓库中取出长度为 length 的木材。如果没有刚好长度的木材,取 出仓库中存在的和要求长度最接近的木材。如果有多个符合要求,取出比较短。输出取出的木材长度。如果仓库为空,输出 Empty

输入:

7
1 1
1 5
1 3
2 3
2 3
2 3
2 3

输出:

3
1
5
Empty
2.2 思想

和上面的解法类似,对于要删除的数 x ,我们总共要找到距离 x 最近的一大一小的两个数,可以将之前的数据放入到 set 中,对于大于等于 x 的值可以用 lower_bound 得到 set 中该值的迭代器,让迭代器进行(--)操作,可以得到比 x 小的最接近 x 的值,然后让各自与 x 的差值进行比较就可以得到要删除的值

值得注意的是:当对迭代器进行(--)操作时,如果 set 里的元素不够,可能非法访问,所以我们需要左右护法进行保护,而左右护法也不能干涉比较的结果,那左右护法可以趋于无穷(即这个情况下不可能取到的值)

2.3 模拟实现

#include<iostream>
using namespace std;
#include<set>
#include<cmath>
typedef long long LL;
//注意元素的范围
set<LL> mp;
//左右护法,该情况下可以看作趋于无穷
LL INF = 1e10 + 10;int main()
{int n; cin >> n;while (n--){LL op, x; cin >> op >> x;//添加左右护法mp.insert(INF); mp.insert(-INF);if (op == 1){//如果 set 没有就插入if (mp.count(x)) cout << "Already Exist" << endl;else mp.insert(x);}else{//只有左右护法可以将 set 看作空if (mp.size() == 2) cout << "Empty" << endl;else{//取出大于等于 x 的值的迭代器auto it1 = mp.lower_bound(x);//找到最近的小于 x 的迭代器auto it2 = it1;it2--;//进行比较if (abs(*it1 - x) >= abs(*it2 - x)){cout << *it2 << endl;mp.erase(*it2);}else{cout << *it1 << endl;mp.erase(*it1);}}}}return 0;
}

相关文章:

set 和 map 的左右护卫 【刷题反思】

1. 相近的营业额 1.1 题目 题目描述&#xff1a;我们定义&#xff0c;一天营业额的最小波动 min { | 该天以前某一天的营业额 - 该天营业额 | } 特别的&#xff0c;第一天的营业额最小波动为第一天的营业额 输入描述&#xff1a;第一行 n &#xff08;n < 32767&#xf…...

【Linux高级IO】多路转接(poll epoll)

目录 1. poll 2. epoll 2.1 epoll_ctl 2.2 epoll_wait 2.3 epoll原理 2.4 epoll的工作模式 2.5 epoll的惊群效应 使用建议 总结 1. poll poll也是实现 I/O 多路复用的系统调用&#xff0c;可以解决select等待fd上限的问题&#xff0c;将输入输出参数分离&#xff0c;不需要…...

Linux上用C++和GCC开发程序实现两个不同PostgreSQL实例下单个数据库中多个Schema稳定高效的数据迁移到其它PostgreSQL实例

设计一个在Linux上运行的GCC C程序&#xff0c;同时连接三个不同的PostgreSQL实例&#xff0c;其中两个实例中分别有两个数据库中多个Schema的表结构分别与第三实例中两个数据库中多个Schema个结构完全相同&#xff0c;同时复制两个实例中两个数据库中多个Schema里的所有表的数…...

Linux下的网络通信编程

在不同主机之间&#xff0c;进行进程间的通信。 1解决主机之间硬件的互通 2.解决主机之间软件的互通. 3.IP地址&#xff1a;来区分不同的主机&#xff08;软件地址&#xff09; 4.MAC地址&#xff1a;硬件地址 5.端口号&#xff1a;区分同一主机上的不同应用进程 网络协议…...

Windows在多网络下指定上网接口

Windows在多网络下指定上网接口 一、说明 设备情况&#xff1a;win11&#xff0c;同时连接了有线网和WLAN&#xff0c;有线网连接着NAS必须保持连接。需求&#xff1a;有些情况时&#xff0c;有线网无网络而WLAN有网&#xff0c;但系统仍走着有线导致无法上网。 二、方法 过…...

网络安全员证书

软考网络安全员证书&#xff1a;信息安全领域的黄金标准 随着信息技术的飞速发展&#xff0c;网络安全问题日益凸显&#xff0c;网络安全员的需求也日益增加。软考网络安全员证书作为信息安全领域的黄金标准&#xff0c;对于网络安全从业者来说具有重要意义。本文将详细介绍…...

CMU15445(2023fall) Project #4 - Concurrency Control踩坑历程

把树木磨成月亮最亮时的样子&#xff0c; 就能让它更快地滚下山坡&#xff0c; 有时会比骑马还快。 完整代码见&#xff1a; SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering…...

医疗AR眼镜:FPC如何赋能科技医疗的未来之眼?【新立电子】

随着科技的飞速发展&#xff0c;增强现实&#xff08;AR&#xff09;技术在医疗领域的应用逐渐成为焦点。医疗AR眼镜作为一种前沿的智能设备&#xff0c;正在为医疗行业带来深刻的变革。它不仅能够提升医生的工作效率&#xff0c;还能改善患者的就医体验&#xff0c;成为医疗科…...

Python从0到100(八十九):Resnet、LSTM、Shufflenet、CNN四种网络分析及对比

前言&#xff1a; 零基础学Python&#xff1a;Python从0到100最新最全教程。 想做这件事情很久了&#xff0c;这次我更新了自己所写过的所有博客&#xff0c;汇集成了Python从0到100&#xff0c;共一百节课&#xff0c;帮助大家一个月时间里从零基础到学习Python基础语法、Pyth…...

服务器迁移记录【腾讯云-->阿里云】

准备工作 压缩/root /usr/local/nginx /data三个目录到zip&#xff0c;并下载到本地。 zip root.zip /root zip nginx.zip /usr/local/nginx zip data.zip /datasz root.zip sz nginx.zip sz data.zip连接mysql数据库&#xff0c;导出数据库结构与数据到dzs_mysql.sql 安装l…...

序列化选型:字节流抑或字符串

序列化既可以将对象转换为字节流&#xff0c;也可以转换为字符串&#xff0c;具体取决于使用的序列化方式和场景。 转换为字节流 常见工具及原理&#xff1a;在许多编程语言中&#xff0c;都有将对象序列化为字节流的机制。例如 Python 中的 pickle 模块、Java 中的对象序列化…...

面向实时性的超轻量级动态感知视觉SLAM系统

一、重构后的技术架构设计(基于ROS1 ORB-SLAM2增强) #mermaid-svg-JEJte8kZd7qlnq3E {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-JEJte8kZd7qlnq3E .error-icon{fill:#552222;}#mermaid-svg-JEJte8kZd7qlnq3E .…...

4-3自定义加载器,并添加功能

一、自定义类加载器的实现步骤 ​继承ClassLoader类​ 自定义类加载器需继承java.lang.ClassLoader&#xff0c;并选择性地重写以下方法&#xff1a; ​findClass(String name)&#xff1a;核心方法&#xff0c;用于根据类名查找并加载类的字节码。需从自定义路径&#xff08…...

Python Scrapy爬虫面试题及参考答案

目录 简述 Scrapy 框架的基本工作流程,并说明各组件的作用 Scrapy 中的 Spider、CrawlSpider 和 Rule 的作用及区别? 如何通过 Scrapy Shell 快速调试页面解析逻辑? Scrapy 的 start_requests 方法与 start_urls 的关系是什么? 解释 Scrapy 的 Request 和 Response 对象…...

Swan 表达式 - 选择表达式

ANSYS Swan 表达式支持选择(selection)表达式 case, if/then/else。选择表达式根据特定的条件选择不同的分支流。 if/then/else 表达式 if/then/else 表达式的文法如下 if expr then expr else expr 其中&#xff0c;首个expr 的布尔表达式&#xff0c;若其为 true, 则返回 …...

微信小程序:完善购物车功能,购物车主页面展示,详细页面展示效果

一、效果图 1、主页面 根据物品信息进行菜单分类&#xff0c;点击单项购物车图标添加至购物车&#xff0c;记录总购物车数量 2、购物车详情页 根据主页面选择的项&#xff0c;根据后台查询展示到页面&#xff0c;可进行多选&#xff0c;数量加减等 二、代码 1、主页面 页…...

javaweb将上传的图片保存在项目文件webapp下的upload文件夹下

前端HTML表单 (upload.html) 首先&#xff0c;创建一个HTML页面&#xff0c;允许用户选择并上传图片。 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>图片上传</title> </head> <…...

LabVIEW 无法播放 AVI 视频的编解码器解决方案

用户在 LabVIEW 中使用示例程序 Read AVI File.vi&#xff08;路径&#xff1a; &#x1f4cc; C:\Program Files (x86)\National Instruments\LabVIEW 2019\examples\Vision\Files\Read AVI File.vi&#xff09;时发现&#xff1a; ✅ LabVIEW 自带的 AVI 视频可正常播放 这是…...

composer 错误汇总

文章目录 1: 安装EasyWeChat 报错2: composer install 报错, laravel/framework[v11.9.0, ..., v11.44.0] require fruitcake/php-cors ^1.33: 卸载Pulse 报错, Class "Laravel\Pulse\Pulse" not found4: 卸载Telescope报错 1: 安装EasyWeChat 报错 解决: composer …...

MySQL锁分类

一、按锁的粒度划分 全局锁 定义&#xff1a;锁定整个数据库实例&#xff0c;阻止所有写操作&#xff0c;确保数据备份一致性。加锁方式&#xff1a;通过FLUSH TABLES WITH READ LOCK实现&#xff0c;释放需执行UNLOCK TABLES。应用场景&#xff1a;适用于全库逻辑备份&#xf…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...