虚拟内存（P2318）

· · 题解

我看了该题的几篇题解，什么map+set,什么线段树，抱歉我都不会

蒟蒻的方法，大佬勿喷。

实际上只需一个优先队列就能过了，并且跑得贼快。。。。。。

用普通数组存不下1e9，离散就行了。

关于排序的优先级，直接先按照出现的次数排序，再按照时间排序，刚开始打时，我把大于小于弄反了，卡了好几个小时。。。。。。

  1. 若内存未被排满，直接将其塞入。

  2. 若已排满，其实当前页在不在队列中都不重要，遇到已经存在页就加1即可。因此可以直接通过取队首元素，将其出队直到能够放置时就行了。

直接见我精简但无脑的代码：

#include<iostream>
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
struct node {
    int xu,t;
    bool operator<(const node &a)const {
        if(t==a.t)return xu>a.xu;
        return t>a.t;
    }
};
priority_queue<node>q;
int a[maxn],b[maxn];
int num[maxn];
int main() {
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1; i<=m; i++)scanf("%d",&a[i]),b[i]=a[i];
    sort(b+1,b+m+1);
    int k=unique(b+1,b+m+1)-b-1;
    int tot=0,ans=0;
    for(int i=1; i<=m; i++) {
        a[i]=lower_bound(b+1,b+k+1,a[i])-b;
        if(num[a[i]])num[a[i]]++,ans++;
        else if(tot<n)tot++,num[a[i]]=1;
        else {
            node res=q.top();
            q.pop();
            while(num[a[res.xu]]!=res.t)res=q.top()，q.pop();
            num[a[i]]++,num[a[res.xu]]=0;
        }
        q.push((node)<%i,num[a[i]]%>);
    }
    printf("%d\n",ans);
    return 0;
}