题目描述:
【深基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
代码:
#include<cstdio>
#include<set>
using namespace std;
set<int> s;
int main(){
int m;
scanf("%d", &m);
while(m--){
int op,len;
scanf("%d%d", &op, &len);
if(op == 1){
if(s.count(len)){
printf("Already Exist\n"); continue;
}else{
s.insert(len);
}
}else{
if(s.size() == 0){
printf("Empty\n"); continue;
}
auto iter = s.lower_bound(len);//iter -> set<int>::iterator
// *iter -> 解引用
if(iter == s.end()){
iter --;
printf("%d\n", *iter); s.erase(iter);
}else if(iter == s.begin()){//最小的都 >= len
printf("%d\n", *iter); s.erase(iter);
}else{
auto tmp = iter; tmp --;
if(len - *tmp <= *iter - len){
printf("%d\n", *tmp); s.erase(tmp);
}else{
printf("%d\n", *iter); s.erase(iter);
}
}
}
}
return 0;
}