题解：P2318 [HNOI2005] 虚拟内存

思路：
#

定义三个 unordered_map，两个 unordered_map 的键和值都是 int 类型，分别存被访问的次数定义名字为 $mp$ 和是在什么时候存进来的定义名字为 $jl$，第三个 unordered_map 的键为 int 类型，而值为 vector 数组，用来存访问次数为键的内存页是几定义名字为 $se$。

定义 $c$ 为需要访问的虚拟内存页的编号，再定义一个 $minn$ 表示现在最少的访问次数。

如果要访问的内存页存在也就是 mp.count(c) 为一，那么让我们的答案加一，然后把 $se$ 里的数组里的 $c$ 删除，接着把 $c$ 加入到 $se$ 的键为这次操作后 $c$ 被访问的次数的数组里，然后判断一下在这次操作后原本 $se$ 的键为 $minn$ 的数组大小是否为零，如果为零则代表 $c$ 原本是这个数组里唯一的元素，而 $c$ 的访问次数增加后，这个数组里就没有元素了，也就是最少的访问次数现在不是 $minn$ 了而是 $minn$ 加上一，我们让 $minn$ 加一。

如果要访问的内存页不存在，则先判断一下现在 $mp$ 里键的数量是否小于 $n$：
如果小于 $n$，则把 $mp_c$ 赋值为一，然后将 $jl_c$ 赋值为现在是第几个操作，然后在 $se$ 里键为一的数组里加入 $c$，最后把 $minn$ 赋值为一，因为 $c$ 是刚刚加入的，所以只被访问了一次，是最少的访问次数。
如果不小于 $n$ 则把 $se$ 里键为 $minn$ 的数组里的第一个值删除并把 $c$ 加入 $se$ 里键为一的数组里。

代码：
#

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
int n,m,ans=0; 
unordered_map<int,int>mp;// 被访问的次数 
unordered_map<int,int>jl;// 是在什么时候存进来的 
unordered_map<int,vector<int> >se;// 访问次数，是什么 
int minn=1e9;// 最少的访问次数 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    jl[int(1e9+1)]=m+1;
    int c;
    for(int i=1;i<=m;i++){
        cin>>c;
        if(mp.count(c)){
            ans++;
            auto it=find(se[mp[c]].begin(),se[mp[c]].end(),c);
            se[mp[c]].erase(it);
            if(se[minn].size()==0)minn++;
            mp[c]++;
            se[mp[c]].push_back(c);
        }
        else{
            if(mp.size()<n){
                mp[c]=1;
                jl[c]=i;
                se[mp[c]].push_back(c);
                minn=1;
            }
            else{
                int sanc=1e9+1;
                auto it=se.begin();
                vector<int>sz(se[minn]);
                sanc=sz[0];
                auto itt=find(se[mp[sanc]].begin(),se[mp[sanc]].end(),sanc);
                se[mp[sanc]].erase(itt);
                if(se[mp[sanc]].size()==0)se.erase(mp[sanc]);
                mp.erase(sanc);
                jl.erase(sanc);
                mp[c]=1;
                jl[c]=i;
                minn=1;
                se[mp[c]].push_back(c);
            }
        }
    }
    cout<<ans;
    return 0;
}

思路： #

代码： #

思路：
#

代码：
#