银行的客户队列【STL 中 Set 和 Pair 的简单使用】

Lokinli

发布于 2023-03-09 14:30:58

3070

发布于 2023-03-09 14:30:58

文章被收录于专栏：以终为始

题解：

如果每次都排序一遍肯定会超时的，可以使用 STL 中自动排序的 Set ，因为是两个数，所以加上 pair 就可以。

如果是2，那就尾部选一个，然后删除掉。

如果是3，就从头选一个，然后删除掉。

加上 pair 排序就是先按第一个排，再按第二个，都是从小到大的顺序。

注意 set 的begin( ) 和 end( ) 。

一开始的憨憨思路：

最初想的是用两个优先队列，一个大的，一个小的，然后开两个map ，一个记录优先值，一个记录是否把该数删除掉，理论上自己臆想还可以哈哈哈，不过后来发现了这样很麻烦，写了会就放弃了，有一些样例不好处理。

正好复习一下 set 和 pair 使用。

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int q,k,p;
    set<pair<int ,int > > st;
    set<pair<int, int> > :: iterator it;
    while(cin >> q && q){
        if(q == 1){
            cin >> k >> p;
            st.insert(make_pair(p,k));
        }
        else if(q == 2){
            if(st.empty()){
                cout << 0 << endl;
            }
            else {
                it = st.end();
                it--;
                cout << it->second << endl;
                st.erase(it);
            }
        }
        else if(q == 3){
            if(st.empty()){
                cout << 0 << endl;
            }
            else {
                it = st.begin();
                cout << it->second << endl;
                st.erase(it);
            }
        }
    }
    return 0;    
}

某个银行很傲娇，来了一些客户，有时先接待优先级最高的客户，有时先接待优先级最低的客户，有如下四种操作：

0：系统停止服务。

1 K P：增加一个 ID 为 K(K\leq 10^6)的客户，其优先级是 P(P\leq 10^7)。

2：查询优先级最高的客户，接待他，并从等候队列里删除。

3：查询优先级最低的客户，接待他，并从等候队列里删除。

你的任务是依次输出这些客户的 ID。