STL之set

木材仓库

题目描述

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

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

样例 #1

样例输入 #1

样例输出 #1

3
1
5
Empty

`set` 解法

该题符合集合具备的特点，可以用 set 解。
set 常见功能
- set<int> st
  - 建立一个元素类型为 int 的集合。
- st.insert(x)
  - 插入元素 x，如果这个元素已存在则什么也不做。
- st.erase(x)
  - 删除元素 x，如果这个元素不存在则什么也不做。
- st.erase(it)
  - 删除迭代器 it对应的元素。
- st.end()
  - 返回集合中最后一个元素的下一位的地址，一般配合其他方法做判断。
- st.find(x)
  - 查询 x 在集合中的地址，如果这个数不存在，则返回 st.end()。
- st.lower_bound(x)
  - 查询大于或等于 \(x\) 的最小的数在集合中的地址，如果这个数不存在，则返回 st.end()。
- st.upper_bound(x)
  - 查询大于 \(x\) 的最小的数在集合中的地址，如果这个数不存在，则返回 st.end()。
- st.empty()
  - 如果集合为空，则返回真值。
- st.size()
  - 集合元素个数。

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set>

int n, x, opt;
std::set<int> st;

int main()
{
 	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	std::cin >> n;
	for (int i = 1; i <= n; i++)
	{
		std::cin >> opt >> x;
		if (opt == 1)
		{
			if (st.find(x) != st.end())
			{
				std::cout << "Already Exist\n";
			}
			else
			{
				st.insert(x); 
			}
		}
		else
		{
			if (st.empty())
			{
				std::cout << "Empty\n";
			}
			else if (st.find(x) != st.end())
			{
				st.erase(x);
				std::cout << x << std::endl;
			} 
			else
			{
				std::set<int>::iterator i = st.lower_bound(x), j = i;//找第一个大于的（等于的已经在上面处理过了）
				if (j != st.begin()) --j;//减去之后是最后一个小于的
				if (i != st.end() && x - (*j) > (*i) - x) j = i;//即从最小的大于x的数和最大的小于x的数之间比较
				std::cout << *j << std::endl;
				st.erase(j);
			}
		}
	}
	return 0;
}