首页 > 其他分享 >洛谷P5250 【深基17.例5】木材仓库

洛谷P5250 【深基17.例5】木材仓库

时间:2024-08-06 21:38:57浏览次数:15  
标签:深基 洛谷 17 仓库 木材 位置 length set 长度

【深基17.例5】木材仓库

题目描述

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

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

输入格式

输出格式

样例 #1

样例输入 #1

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

样例输出 #1

3
1
5
Empty

思路:

  • 这题我们观察到要快速查找仓库中是否存在length长度的木材,而且还要让长度为length的木材出库,有这两个特性我们会自然而然的想到set,能够快速检索,并且还能快速删除集合中的某一个元素。
  • 首先,我们定义一个set,然后循环n次操作,如果x==1的话,我们就查找,查到了就输出Already Exist,并换行。否则,就进入x=2的逻辑,先判断set是否为空,为空我们就输出empty,否则我们就利用lower_bound来查找到第一个大于等于length的位置
  • 让指针i指向set中第一个≥length的位置,先让指针j与指针i指向相同的位置。并且判断i的两个特殊情况:
  1. i指向s.begin()的位置,此时将j赋值为i(不动即可),此时的j就是我们要删除的位置,并记得在删除之前先输出一下
  2. i指向s.end()的位置,此时将j赋值为i-1的位置,就是set中最后一个元素的位置,此时j就是我们要出库的那根木材
  3. 如果i在中间的某一个位置,我们得判断i-1的位置和i的位置哪一个距离length更近,因为lower_bound只是能找出第一个≥length的位置,并不能直接判断上一个位置和找到的这个位置与检索的值哪一个距离更近,因此,我们先让j--,然后判断二者距离length的位置谁更近,如果i距离length更近,只需要将j重新赋值给i就行了
				else {
					j--;
					if (*i - length < length - *j) j = i;
				}
  1. 最后,记得输出j所指向的位置,并在集合中删除j指向的元素即可
				cout << *j << endl;
				//这里可以写*j,也可以只写j,只写j表明删除j这个迭代器所对应的位置,写*j表明删除j所指向的这个元素
				s.erase(*j);

代码:

#include<set>
#include<iostream>
using namespace std;
int n;
int x, length;
set<int> s;
int main()
{
	cin >> n;
	while (n--) {
		cin >> x >> length;
		if (x == 1) {
			if (s.find(length) == s.end()) s.insert(length);
			else cout << "Already Exist" << endl;
		}
		else if (x == 2) {
			if (s.empty()) cout << "Empty" << endl;
			else {
				auto i = lower_bound(s.begin(),s.end(), length);
				auto j = i;
				if (i == s.begin()) j = i;
				else if (i == s.end()) {
					i--; j = i;
				}
				else {
					j--;
					if (*i - length < length - *j) j = i;
				}
				cout << *j << endl;
				s.erase(*j);
			}
		}
	}
	return 0;
}

标签:深基,洛谷,17,仓库,木材,位置,length,set,长度
From: https://www.cnblogs.com/Tomorrowland/p/18346038

相关文章

  • Mac开发基础17-NSButton(二)
    NSButton是一个功能强大且灵活多样的控件,除了基本使用和常见API外,还有一些进阶用法和技巧可以提高按钮的可用性和实现细节。在以下内容中,我会详细介绍一些进阶使用技巧,并封装一个常用的工具类来实现自定义的多种按钮类型。进阶使用和技巧1.自定义按钮的外观和行为Objective-C......
  • odoo17 环境配置
    1、PostgreSql数据库安装教程:Windows上安装PostgreSQL|菜鸟教程(runoob.com) (建议版本15以上)注意:由于Odoo是不允许用pg自带的管理员角色--postgres,所以得创一个odoo使用数据库的角色:createuserodoowithpassword'odoo';alterroleodoowithsuperuser;也可......
  • Navicat Premium(数据库管理) v17 中文授权版
    Navicat17全新升级,软件增强了数据库管理和数据分析的功能体验。其中包括模型设计与同步、数据字典、数据分析(dataprofiling)、用户体验、查询优化、BI功能集成MongoDB/Snowflake、专注模式、Redis哨兵模式与平台扩展LinuxARM等。此次升级让用户在数据库的创建、管理、......
  • 洛谷P1209修理牛棚 Barn Repair
    [USACO1.3]修理牛棚BarnRepair题目描述在一个月黑风高的暴风雨夜,FarmerJohn的牛棚的屋顶、门被吹飞了好在许多牛正在度假,所以牛棚没有住满。牛棚一个紧挨着另一个被排成一行,牛就住在里面过夜。有些牛棚里有牛,有些没有。所有的牛棚有相同的宽度。宽度为1自门遗失以后......
  • 洛谷P1081【NOIP2012提高组】开车旅行
    题目见[NOIP2012提高组]开车旅行-洛谷(懒得打题目了)我们直接上代码#include<iostream>#include<cstdlib>#include<cstdio>#include<cmath>#include<cstring>#include<iomanip>#include<algorithm>#include<ctime>#include<queue>......
  • SQL2017 安装教程图解(详细到每一个细节)
    SQL2017安装教程图解(详细到每一个细节)----bayaim----2024年8月5日15:27:41----借鉴网址:https://blog.csdn.net/weixin_39665379/article/details/111100754 一、程序准备JDK:jdk-7u80-windows-x64(官网可以下最新的,JDK7以上就可以,其他版本没试过不知道可不可以,等我试过......
  • 洛谷题单指南-前缀和差分与离散化-P1904 天际线
    原题链接:https://www.luogu.com.cn/problem/P1904题意解读:给出(左端点,高度,右端点)表示的若干建筑,要输出其轮廓,所谓轮廓就是每个点被覆盖的最高建筑的高度所描绘的线。解题思路:如果能计算每个点被覆盖的最高建筑的高度,用数组h[10005]保存,那么输出轮廓的过程只需要枚举每一个点,如......
  • P4604 [WC2017] 挑战 题解
    题目描述任务一给定\(n\)个\(32\)位无符号整数,将它们从小到大排序。任务二有\(2n\)个人玩"石头剪刀布"游戏,他们分成两排,每排\(n\)个人,\(a_{i,j}=0/1/2\)分别表示第\(i\)排第\(j\)人出石头、剪刀、布。\(q\)次询问,每次给定\(x,y,l\),询问第一排第\(x\simx......
  • nature immunology | BACH2调控“调节性”和“促炎性”TH17细胞的染色质多样化状态
    –https://doi.org/10.1038/s41590-024-01901-1BACH2regulatesdiversificationofregulatoryandproinflammatorychromatinstatesinTH17cells留意更多内容,欢迎关注微信公众号:组学之心研究团队和研究单位AvivRegev–GenentechVijayK.Kuchroo–BroadInsti......
  • 洛谷-P9830 题解
    思路分析分析样例:见红线,长宽各为2,存在格点;黄线长2宽3,没有格点。考虑延长黄线使得长4宽6,发现有格点。思考格点,如果长和宽都可以被分成\(p\timesl\)的格式,则存在格点。那么,就能想出:推论1:对于\((0\,\0)\)和\((x\,\y)\)之间没有格点,当且仅当\(\gcd(x\,......