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

【题目来源】

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

【题目描述】

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

• 进货，格式1 Length：在仓库中放入一根长度为 Length(不超过 \(10^9\)) 的木材。如果已经有相同长度的木材那么输出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

【解题思路】

【算法标签】

《洛谷 P5250 木材仓库》 #集合#

【代码详解】

#include <bits/stdc++.h>
using namespace std;int n, type, length;  // n: 操作次数, type: 操作类型, length: 木材长度
set<int> a;           // 使用set存储木材长度（自动排序且去重）
set<int>::iterator it, itup;  // 迭代器用于查找和遍历int main()
{// 输入操作次数cin >> n;// 处理每个操作for (int i = 0; i < n; i++) {cin >> type >> length;// 查找当前长度是否已存在it = find(a.begin(), a.end(), length);// 操作类型1：添加木材if (type == 1) {if (it == a.end())  // 如果不存在则添加{a.insert(length);}else  // 已存在则提示{cout << "Already Exist" << endl;}}// 操作类型2：取出木材else if (type == 2) {// 处理空集合情况if (a.empty()) {cout << "Empty" << endl;}// 存在完全匹配的木材else if (it != a.end()) {cout << length << endl;a.erase(it);}// 需要找最接近的木材else {// 找到第一个大于length的木材itup = upper_bound(a.begin(), a.end(), length);// 情况1：所有木材都比length小if (itup == a.end()) {itup--;cout << *itup << endl;a.erase(itup);}// 情况2：所有木材都比length大else if (itup == a.begin()) {cout << *itup << endl;a.erase(itup);}// 情况3：需要比较前后两个木材哪个更接近else {itup--;it = itup++;if (length - *it <= *itup - length) {cout << *it << endl;a.erase(it);}else {cout << *itup << endl;a.erase(itup);}}}}}return 0;
}

【运行结果】

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