《洛谷深入浅出基础篇》 P5250 木材仓库————集合应用实例

上链接:

P5250 【深基17.例5】木材仓库 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)icon-default.png?t=N7T8https://www.luogu.com.cn/problem/P5250上题干:

题目描述

博艾市有一个木材仓库,里面可以存储各种长度的木材,但是保证没有两个木材的长度是相同的。作为仓库负责人,你有时候会进货,有时候会出货,因此需要维护这个库存。有不超过 100000 条的操作:

  • 进货,格式1 Length:在仓库中放入一根长度为 Length(不超过 109109) 的木材。如果已经有相同长度的木材那么输出Already Exist
  • 出货,格式2 Length:从仓库中取出长度为 Length 的木材。如果没有刚好长度的木材,取出仓库中存在的和要求长度最接近的木材。如果有多根木材符合要求,取出比较短的一根。输出取出的木材长度。如果仓库是空的,输出Empty

输入格式

输出格式

输入输出样例

输入 #1复制

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

输出 #1复制

3
1
5
Empty

这道题是一道能用set解决的简单题,我们首先介绍一些这道题用到的函数。

1.set.insert() 这个函数其实是有参数返回值的

它的参数是一个pair对

pair.first是   这个数插入的位置,也就是一个迭代器。

pair.second是一个bool值,代表是否插入成功。

所以如果我们要查看是否插入成功只需要访问 insert().second 即可

 

第二个函数:

set.erase()

用处是删除一个元素,或者一片元素

返回值只有1或0代表是否删除成功,如果没有这个数,说明删除失败,返回0;

第三个函数:

set.find()

用途是查找set中的元素。

返回值长这样:

可以看到它是一个迭代器,如果找到了,返回该元素的迭代器,如果没找到,返回end()

第四个函数

set.lower_bound 

二分查找一个数,返回参数如下

可以看到返回的也是一个迭代器,只不过和find函数有所不同的是,

如果集合里面没有这个数字,我们就返回第一个大于等于这个数的迭代器,

倘若,查找的数字比现在集合中的所有数字都大,那么返回的就是end(); 

 

第五个函数,set.empty() 

可以看出,它的返回值是一个bool类型,集合为空时返回1,否则返回0; 

以上就是关于set的用法。

对于这道题,我们用这些函数完全可以完成。

 

int n, op, t;
set<int>::iterator kk, jj, pp;
set<int> s;
int main(){
	cin >> n;
	for (int i = 1;i <= n;i ++){
		cin >> op >> t;
		if (op == 1){
			if (!s.insert(t).second) cout << "Already Exist\n";
		}
		else {
			if (s.empty()){
				cout << "Empty\n";
				continue;
			}
			if (s.find(t) != s.end()) cout << t, s.erase(s.find(t));
			else {
				kk= jj = s.lower_bound(t);
				if (kk == s.begin()) cout << *kk, s.erase(kk);
				else if (kk == s.end()) cout << *(-- kk), s.erase(kk);
				else if (*kk - t < t - *(-- jj)) cout << *(kk), s.erase(kk);
				else cout << *(jj), s.erase(jj);
			}
			cout << endl;
		}
	}
}

当我们的程序运行到这里的时候:

无论进入不进入条件语句,我们的 j迭代器 都会-- ,所以接下来的else 我们直接输出它就好了

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/164922.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Java面向对象(高级)-- 类的成员之四:代码块

文章目录 一、回顾&#xff08;1&#xff09;三条主线&#xff08;2&#xff09;类中可以声明的结构及作用1.结构2.作用 二、代码块&#xff08;1&#xff09;代码块的修饰与分类1. 代码块的修饰2. 代码块的分类3. 举例 &#xff08;2&#xff09; 静态代码块1. 语法格式2. 静态…

两栏布局:左侧固定,右侧自适应

左侧宽度固定&#xff0c;右侧宽度自适应剩余空间 方法一&#xff1a;float margin 方法二&#xff1a;flex布局 相关HTML代码 <div class"container"><div class"left"></div><div class"main"></div> </d…

BGP基本配置

配置逻辑 完成所有路由器的IGP配置使用直连接口建立EBGP对等体关系使用环回接口建立IBGP对等体关系使用connect-interface命令修改IBGP建邻源IP地址使用next-hop-local命令修改路由传递时的下一跳属性若存在使用环回接口建立EBGP对等体关系&#xff0c;则需要建立通讯条件&…

CentOS 7 安装CMake指定版本3.21.2

背景&#xff1a;今天在CentOS 7 电脑上安装C 日志框架SpdLog-1.12.0&#xff0c;提示如下错误信息&#xff1a; [rootlocalhost build]# cmake .. && make -j CMake Error at CMakeLists.txt:3 (cmake_minimum_required):CMake 3.10...3.21 or higher is required. …

Mysql-索引

1.介绍 索引是数据库管理系统中用于提高查询速度的一种数据结构。在MySQL中&#xff0c;索引可以看作是一种特殊的表&#xff0c;其中包含了对数据表中特定列的值及其在数据表中的位置信息。通过使用索引&#xff0c;MySQL可以在不需要扫描整个表的情况下快速找到与查询条件匹…

三栏布局,中间自适应

方法一&#xff1a;两边使用float 中间使用margin 方法二&#xff1a;两边使用absolute 中间使用margin 方法三&#xff1a;flex 布局 方法四&#xff1a;grid 布局 方法一&#xff1a;相关HTML代码【两边使用float 中间使用margin】 <div class"container"…

类和对象(8):explicit,static成员,友元,内部类

一、explicit class Date { public:Date(int year 2023, int month 1, int day 1):_year(year),_month(month),_day(day){}private:int _year;int _month;int _day; };int main() {// Date d1(1); // 这是正常初始化Date d1 1;return 0; }不妨猜测一下&#xff0c;d1的初始…

2023年【安全员-A证】报名考试及安全员-A证新版试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 安全员-A证报名考试是安全生产模拟考试一点通总题库中生成的一套安全员-A证新版试题&#xff0c;安全生产模拟考试一点通上安全员-A证作业手机同步练习。2023年【安全员-A证】报名考试及安全员-A证新版试题 1、【多选…

LeetCode(29)三数之和【双指针】【中等】

目录 1.题目2.答案3.提交结果截图 链接&#xff1a; 三数之和 1.题目 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复…

SpringBoot-AOP学习案例

4. AOP案例 SpringAOP的相关知识我们就已经全部学习完毕了。最后我们要通过一个案例来对AOP进行一个综合的应用。 4.1 需求 需求&#xff1a;将案例中增、删、改相关接口的操作日志记录到数据库表中 就是当访问部门管理和员工管理当中的增、删、改相关功能接口时&#xff0…

单线程的JS中Vue导致的“线程安全”问题

目录 现象分析原因 浏览器中Js是单线程的&#xff0c;当然不可能出现线程安全问题。只是遇到的问题的现象与多线程的情况十分相似&#xff0c;导致对不了解Vue实现的我怀疑起了人生… 现象 项目中用到了element-plus中的加载组件&#xff0c;简单封装了一下&#xff0c;用来保…

100.相同的树(LeetCode)

关于树的递归问题&#xff0c;永远考虑两方面&#xff1a;返回条件和子问题 先考虑返回条件&#xff0c;如果当前的根节点不相同&#xff0c;那就返回false&#xff08;注意&#xff0c;不要判断相等时返回什么&#xff0c;因为当前相等并不能说明后面节点相等&#xff0c;所以…

【每日一题】689. 三个无重叠子数组的最大和-2023.11.19

题目&#xff1a; 689. 三个无重叠子数组的最大和 给你一个整数数组 nums 和一个整数 k &#xff0c;找出三个长度为 k 、互不重叠、且全部数字和&#xff08;3 * k 项&#xff09;最大的子数组&#xff0c;并返回这三个子数组。 以下标的数组形式返回结果&#xff0c;数组中…

a标签下载文件与解决浏览器默认打开某些格式文件的问题

前言 在实际项目中&#xff0c;我们通常会遇到这么一个需求&#xff1a;后端给前端返回一个任意文件类型的完整的url路径&#xff0c;前端拿到这个路径直接通过浏览器下载文件到本地。我想大家应该都会首先想到使用HTML中的<a>标签&#xff0c;&#xff0c;因为<a>…

【深度学习实验】注意力机制(二):掩码Softmax 操作

文章目录 一、实验介绍二、实验环境1. 配置虚拟环境2. 库版本介绍 三、实验内容0. 理论介绍a. 认知神经学中的注意力b. 注意力机制&#xff1a; 1. 注意力权重矩阵可视化&#xff08;矩阵热图&#xff09;2. 掩码Softmax 操作a. 导入必要的库b. masked_softmaxc. 实验结果 ​ …

代码随想录算法训练营第25天|216.组合总和III 17.电话号码的字母组合

JAVA代码编写 216. 组合总和III 找出所有相加之和为 n 的 k 个数的组合&#xff0c;且满足下列条件&#xff1a; 只使用数字1到9每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次&#xff0c;组合可以以任何顺序返回。 示例 1: 输入: k …

Spring IOC/DI和MVC及若依对应介绍

文章目录 一、Spring IOC、DI注解1.介绍2.使用 二、Spring MVC注解1.介绍2.使用 一、Spring IOC、DI注解 1.介绍 什么是Spring IOC/DI&#xff1f; IOC(Inversion of Control&#xff1a;控制反转)是面向对象编程中的一种设计原则。其中最常见的方式叫做依赖注入&#xff08;…

windows排除故障工具pathping、MTR、sysinternals

pathping 基本上可以认为它是ping和tracert的功能合体。 pathping首先对目标执行tracert&#xff0c;然后使用ICMP对每一跳进行100次ping操作。 如图&#xff0c;是一个对8.8.8.8进行pathing操作。 MTR MTR是另一个多工具合体工具。 winmtr是mtr的windows版本。 这个工具…

c盘清除文件

打开设置 搜索存储

设计模式(二)-创建者模式(2)-工厂模式

一、为何需要工厂模式&#xff08;Factory Pattern&#xff09;? 由于简单工厂模式存在一个缺点&#xff0c;如果工厂类创建的对象过多&#xff0c;使得代码变得越来越臃肿。这样导致工厂类难以扩展新实例&#xff0c;以及难以维护代码逻辑。于是在简单工厂模式的基础上&…