洛谷——P5250 【深基17.例5】木材仓库(set做法、c++)

发布时间:2023年12月26日


一、题目

【深基17.例5】木材仓库

题目描述

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

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

二、题解

  • 基本思路:
  • 可以把存木材的仓库看作一个集合,题中又说了“保证没有两个木材的长度是相同的”,所以可以用STL中的set来存放木材。
  • s.count(x)返回集合中元素x的个数,可以判断集合中有没有元素x,当然这里用的是set,存放的是不同的元素,如果有元素x也只有一个。
  • s.erase(k),这里的k是指的迭代器,作用是删除迭代器k所指向的元素。
  • 有几个易错点,我中招了(>﹏<)。一个是使用lower_bound()二分查找是需要设置边界,否则–lower_bound(x)(指的是找到第一个大于等于x的元素的前一个元素的迭代器),可能会越界导致报错RE。
  • 另一个就是边界应设置大些,远大于1e9,刚开始设置的1e9+10,会W两个点,因为出货时需要找到与x长度最接近的木材,如果边界设置小了,答案可能会取到边界。
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl "\n"
#define int long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound

const int INF = 1e12+10;
set<int> s;//存放木材 
int num=0;//目前有几个木材 

void solve(){
	int op,x;
	cin>>op>>x;
	if(op==1){
		if(s.count(x))
		  cout<<"Already Exist"<<endl;
		else
		  s.insert(x);//存放长度为x木材  
	}else if(op==2){
		if(s.size()==2)
		  cout<<"Empty"<<endl;
		else {
			auto k=s.lb(x);
			if(*k==x){//有刚好长度的木材 
				cout<<x<<endl;
				s.erase(k);
			}else{
				auto k1=s.lb(x),k2=--s.lb(x);//找到长度接近x的木材 
				if(abs(*k1-x)<abs(*k2-x)){ 
					cout<<*k1<<endl;
					s.erase(k1); 
				}else{//取最接近x且比较短的一根木材
					cout<<*k2<<endl;
					s.erase(k2); 
				}
			}
		}
	} 
	
	
}

signed main(){
	IOS;
	s.insert(INF),s.insert(-INF);
	int T=1;
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}
文章来源:https://blog.csdn.net/2301_77012063/article/details/135223663
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。