STL之set

木材仓库

题目描述

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

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;
  }