题意

仓库

两种操作

• 入仓库木材
  • 不能有长度相同的(暗示要set或map等)
  • 如果有有长度相同的就输出Already Exist
• 出仓库木材
  • 如果没有木材就输出Empty
  • 如有相同长度的就出相同长度的木材
  • 如果没有相同长度的就出离长度差最小的木材(暗示要重定义)
    • 如果有多个长度差最小且相等的木材就出编号小的

数据

操作条数$<100000$

木材长度$<10^9$ (暗示不能用普通数组做)

思路

一道出入元素的模拟题

优先队列就是好用

废话不多说,讲思路

模拟题其实没有什么思路

我只讲这道题的难点

这道题难在如何找到符合的木材出仓

首先提供两点思路,但都是与排序有关的

就是此题目有两种做法

• priority_queue
• sort

我们需要进行排序求出最符合的木材

当然,肯定要自定义

但是我们用sort的话会多走循环

然后我们最近学了优先队列

我们就可以用优先队列写这道题

存储木材方面我使用的是map,set也是可以的,只是我开始是用map,不想改为set

具体看代码

代码

#include<iostream>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
map<int,bool>m;//长度,是否有
struct no
{
	int x,y;//x为两根木材的距离,y为木材的长度
	bool operator < (const no n)const//重载运算符
	{
		if(y==n.y)//在距离相等时
		{
			return x>n.x;//返回编码小的
		}
		return y>n.y;//否则返回距离短的
	}
};
int main()
{
    int n;
    cin>>n;//输入
    for(int i=0;i<n;i++)
    {
        int op,x;
        cin>>op>>x;//输入
        if(op==1)//进货
        {
            if(m[x])//查看是否有了,本人更推荐使用find
            {
                cout<<"Already Exist\n";//输出
            }
            else
            {
                m[x]=1;//标记为有的
            }
        }
        if(op==2)//出货
        {
            if(m.empty())//判空
            {
                cout<<"Empty\n";//输出
            }
            else
            {
                int id;
                priority_queue<no>q;//存储每个木头的符合度,越符合越前面
                for(auto j:m)//c++11后的迭代变量
                {
                    int l=abs(j.first-x);//计算距离,幼稚园的数学
                    q.push({j.first,l});//入队
                }
                id=q.top().x;//取出最符合的那个木材
                m[id]=0;//可以不加,之前的调试,当作防伪标记算了
                m.erase(id);//清掉,木材出仓
                cout<<id<<"\n";//输出
            }
        }
    }
    return 0;//完结散花
}

题意

模拟题不用讲题意了吧

思路

肯定用 set 啊，能去重又能排序！

将木头入库时检测有没有长度一样的木头：a.find(n) != a.end()

出库时找木头：

• 仓库空了：a.empty()
• 找最近的木头：使用 lower_bound(n)

lower_bound(n)：以 $n$ 为分界线，$n$ 及它后面为下界。取下界中离分界线最近的数，返回这个数的迭代器。

用 lower_bound(n) 先找到离 $n$ 最近的且大于等于 $n$ 的数，然后迭代器往前一格，得到比 $n$ 小的离 $n$ 最近的数。比较大的数和小的数谁离 $n$ 更近，输出更近的数。一样近就输出小的。

代码

#include <bits/stdc++.h>
using namespace std;
set<int> a;
int main(int argc, char **argv){
	int t;
	cin >> t;
	while(t--){
		int op,n;
		scanf("%d %d",&op,&n);
		if (op == 1){
			if(a.find(n) != a.end()){
				printf("Already Exist\n");
				continue;
			}
			a.insert(n);
		}else{
			if (a.empty()){
				printf("Empty\n");
				continue;
			}
			auto it = a.lower_bound(n);
			int r = *it;	// 大的数
			if (it != a.begin())	it--;
			int l = *it;	// 小的数
			if (abs(n - r) < abs(n - l))	printf("%d\n",r),a.erase(r);	// 大的数更近
			else	printf("%d\n",l),a.erase(l);	// 一样近或者小的更近
		}
	}
	return 0;
}

题意

维护一个集合，使其满足查找（无则插入）与删除（距离最近元素）的操作。

思路

既然是集合，就用set，然后声明两个函数，一个进货，一个出货。然后用内置函数。删除用一个迭代器上下找就好了。

代码

以后我就不发完整代码了。因为有些人看题解不动脑子。所以我就发个框架，两个函数怎么写就看着思路写。不要抄！

#include<iostream>
#include<set>
using namespace std;
set<int> a;
int main(){
	void in(int);//进货 
	void out(int);//出货 
	int n(0);//操作次数 
	cin>>n;
	while(n--){
		int mode(0);//模式
		int length(0);
		cin>>mode>>length;
		if(mode==1)
			in(length);
		if(mode==2)
			out(length);
	}
	return 0;//完结撒花！ 
}

题意

模拟题不用讲题意了吧

思路

肯定用 set 啊，能去重又能排序！

将木头入库时检测有没有长度一样的木头：a.find(n) != a.end()

出库时找木头：

• 仓库空了：a.empty()
• 找最近的木头：使用 lower_bound(n)

lower_bound(n)：以 $n$ 为分界线，$n$ 及它后面为下界。取下界中离分界线最近的数，返回这个数的迭代器。

用 lower_bound(n) 先找到离 $n$ 最近的且大于等于 $n$ 的数，然后迭代器往前一格，得到比 $n$ 小的离 $n$ 最近的数。比较大的数和小的数谁离 $n$ 更近，输出更近的数。一样近就输出小的。

代码

#include <bits/stdc++.h>
using namespace std;
set<int> a;
int main(int argc, char **argv){
	int t;
	cin >> t;
	while(t--){
		int op,n;
		scanf("%d %d",&op,&n);
		if (op == 1){
			if(a.find(n) != a.end()){
				printf("Already Exist\n");
				continue;
			}
			a.insert(n);
		}else{
			if (a.empty()){
				printf("Empty\n");
				continue;
			}
			auto it = a.lower_bound(n);
			int r = *it;	// 大的数
			if (it != a.begin())	it--;
			int l = *it;	// 小的数
			if (abs(n - r) < abs(n - l))	printf("%d\n",r),a.erase(r);	// 大的数更近
			else	printf("%d\n",l),a.erase(l);	// 一样近或者小的更近
		}
	}
	return 0;
}