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 题目 题目描述:我们定义,一天营业额的最小波动 min { | 该天以前某一天的营业额 - 该天营业额 | } 特别的,第一天的营业额最小波动为第一天的营业额 输入描述:第一行 n (n < 32767…...
【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 多路复用的系统调用,可以解决select等待fd上限的问题,将输入输出参数分离,不需要…...
Linux上用C++和GCC开发程序实现两个不同PostgreSQL实例下单个数据库中多个Schema稳定高效的数据迁移到其它PostgreSQL实例
设计一个在Linux上运行的GCC C程序,同时连接三个不同的PostgreSQL实例,其中两个实例中分别有两个数据库中多个Schema的表结构分别与第三实例中两个数据库中多个Schema个结构完全相同,同时复制两个实例中两个数据库中多个Schema里的所有表的数…...
Linux下的网络通信编程
在不同主机之间,进行进程间的通信。 1解决主机之间硬件的互通 2.解决主机之间软件的互通. 3.IP地址:来区分不同的主机(软件地址) 4.MAC地址:硬件地址 5.端口号:区分同一主机上的不同应用进程 网络协议…...
Windows在多网络下指定上网接口
Windows在多网络下指定上网接口 一、说明 设备情况:win11,同时连接了有线网和WLAN,有线网连接着NAS必须保持连接。需求:有些情况时,有线网无网络而WLAN有网,但系统仍走着有线导致无法上网。 二、方法 过…...
网络安全员证书
软考网络安全员证书:信息安全领域的黄金标准 随着信息技术的飞速发展,网络安全问题日益凸显,网络安全员的需求也日益增加。软考网络安全员证书作为信息安全领域的黄金标准,对于网络安全从业者来说具有重要意义。本文将详细介绍…...
CMU15445(2023fall) Project #4 - Concurrency Control踩坑历程
把树木磨成月亮最亮时的样子, 就能让它更快地滚下山坡, 有时会比骑马还快。 完整代码见: SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering…...
医疗AR眼镜:FPC如何赋能科技医疗的未来之眼?【新立电子】
随着科技的飞速发展,增强现实(AR)技术在医疗领域的应用逐渐成为焦点。医疗AR眼镜作为一种前沿的智能设备,正在为医疗行业带来深刻的变革。它不仅能够提升医生的工作效率,还能改善患者的就医体验,成为医疗科…...
Python从0到100(八十九):Resnet、LSTM、Shufflenet、CNN四种网络分析及对比
前言: 零基础学Python:Python从0到100最新最全教程。 想做这件事情很久了,这次我更新了自己所写过的所有博客,汇集成了Python从0到100,共一百节课,帮助大家一个月时间里从零基础到学习Python基础语法、Pyth…...
服务器迁移记录【腾讯云-->阿里云】
准备工作 压缩/root /usr/local/nginx /data三个目录到zip,并下载到本地。 zip root.zip /root zip nginx.zip /usr/local/nginx zip data.zip /datasz root.zip sz nginx.zip sz data.zip连接mysql数据库,导出数据库结构与数据到dzs_mysql.sql 安装l…...
序列化选型:字节流抑或字符串
序列化既可以将对象转换为字节流,也可以转换为字符串,具体取决于使用的序列化方式和场景。 转换为字节流 常见工具及原理:在许多编程语言中,都有将对象序列化为字节流的机制。例如 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,并选择性地重写以下方法: findClass(String name):核心方法,用于根据类名查找并加载类的字节码。需从自定义路径(…...
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 其中,首个expr 的布尔表达式,若其为 true, 则返回 …...
微信小程序:完善购物车功能,购物车主页面展示,详细页面展示效果
一、效果图 1、主页面 根据物品信息进行菜单分类,点击单项购物车图标添加至购物车,记录总购物车数量 2、购物车详情页 根据主页面选择的项,根据后台查询展示到页面,可进行多选,数量加减等 二、代码 1、主页面 页…...
javaweb将上传的图片保存在项目文件webapp下的upload文件夹下
前端HTML表单 (upload.html) 首先,创建一个HTML页面,允许用户选择并上传图片。 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><title>图片上传</title> </head> <…...
LabVIEW 无法播放 AVI 视频的编解码器解决方案
用户在 LabVIEW 中使用示例程序 Read AVI File.vi(路径: 📌 C:\Program Files (x86)\National Instruments\LabVIEW 2019\examples\Vision\Files\Read AVI File.vi)时发现: ✅ 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锁分类
一、按锁的粒度划分 全局锁 定义:锁定整个数据库实例,阻止所有写操作,确保数据备份一致性。加锁方式:通过FLUSH TABLES WITH READ LOCK实现,释放需执行UNLOCK TABLES。应用场景:适用于全库逻辑备份…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关
在水泥厂的生产流程中,工业自动化网关起着至关重要的作用,尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关,为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多,其中不少设备采用Devicenet协议。Devicen…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
阿里云Ubuntu 22.04 64位搭建Flask流程(亲测)
cd /home 进入home盘 安装虚拟环境: 1、安装virtualenv pip install virtualenv 2.创建新的虚拟环境: virtualenv myenv 3、激活虚拟环境(激活环境可以在当前环境下安装包) source myenv/bin/activate 此时,终端…...
基于单片机的宠物屋智能系统设计与实现(论文+源码)
本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢,连接红外测温传感器,可实时精准捕捉宠物体温变化,以便及时发现健康异常;水位检测传感器时刻监测饮用水余量,防止宠物…...
