当前位置: 首页 > 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…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

vue3 字体颜色设置的多种方式

在Vue 3中设置字体颜色可以通过多种方式实现&#xff0c;这取决于你是想在组件内部直接设置&#xff0c;还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法&#xff1a; 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...

OkHttp 中实现断点续传 demo

在 OkHttp 中实现断点续传主要通过以下步骤完成&#xff0c;核心是利用 HTTP 协议的 Range 请求头指定下载范围&#xff1a; 实现原理 Range 请求头&#xff1a;向服务器请求文件的特定字节范围&#xff08;如 Range: bytes1024-&#xff09; 本地文件记录&#xff1a;保存已…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...