清理杂物

题目

来源：广州大学第十四届ACM大学生程序设计竞赛（同步赛）

天空度假山庄里的物品实在是太多了，Madeline 想要帮 Oshiro 先生清理这些物品。
但物品对于未来而言都是可能有用的。
于是 Madeline 想出了一个方法，给每一个物品定义一个优先级，如果某个物品的最近使用过，那么它的优先级就更高。例如有两个物品，一个物品 A 在之前使用过，另一个物品 B 在物品 A 最后一次使用之后都没有使用过，那么物品 A 的优先级就比物品 B 的优先级高。
天空度假山庄的容量是有限的，只能存放 个物品，那么优先级前 大的物品就会被留下，而优先级比第 个物品优先级还要小的物品就会被扔掉。如果被扔掉的物品或者本来就没有的物品想要使用的话，就需要将物品购买回来使用。
一开始天空度假山庄中有 个物品，以及每一个物品的编号 和每一个物品的优先级的相对顺序。接下来的 天，每一天会使用一个编号为 的物品，你需要知道这一个物品是否需要购买。

解题思路

表示编号为 的物品的优先级。如果值为 0，表示山庄中不存在该物品。
使用 将优先级与物品对应。数据结构 不仅可以根据优先级快速得出物品编号，还将物品按照优先级从小到大的顺序进行排列。
变量 记录物品之间的相对优先级。

给定一个物品编号 ，

• 如果 ，表示该物品存在于山庄，不需要购买，同时，将其优先级提高至目前最高。
• 如果该物品不存在，则需要购买。
  如果山庄还没有满，则直接将该物品加入 ，并记录优先级（当前最高）。
  如果山庄满了，将优先级最低的物品从 中删除，将新物品加入，更新优先级。

C++代码

#include<cstdio>
#include<map>
using namespace std;

const int maxn = 1e7+5;
long long level[maxn];

int main(){
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    map<long long, int> mp;
    int a;
    for(int i=1; i<=n; ++i){
        scanf("%d", &a);
        mp[i] = a;
        level[a] = i;
    }
    long long num = n+1;
    for(int i=0; i<q; ++i){
        scanf("%d", &a);
        if(level[a]){
            printf("no\n");
            mp.erase(level[a]);
        }
        else{
            printf("yes\n");
            if(mp.size()==m){
                auto it = mp.begin();
                level[it->second] = 0;
                mp.erase(it);
            }
        }
        level[a] = num;
        mp[num] = a;
        ++num;
    }
}