3028: 【普及/提高-】【P5250】木材仓库

内存限制：128 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：4 解决：3

题目描述

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

  • 进货，格式1 Length：在仓库中放入一根长度为 Length(不超过 lns="http://www.w3.org/1998/Math/MathML">109) 的木材。如果已经有相同长度的木材那么输出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

提示

#include<bits/stdc++.h>
using namespace std;
int n,opt,lenth;
set <int> ds;
int main(){
	cin >> n;
	while (n--) {
		cin >> opt >> lenth;
		if (opt == 1)
		    if (ds.find(lenth) != ds.end()) cout<<"Already Exist" <<endl;
		    else ds.insert(lenth);
		else if(ds.empty())
		    cout << "Empty" <<endl;
		else {
			set <int> ::iterator i = ds.lower_bound(lenth), j = i;
			//需要注意，如果j是ds.begin()，则是不能--的 
			if (j != ds.begin()) --j;
			if (i != ds.end() && lenth -(*j) > (*i) - lenth) j = i;
			//若i是end(),则不能对i解引用 
			cout << (*j) << endl, ds.erase(j); 
		}
	}

	return 0;
}

来源/分类

提交提交记录统计露一手!