题解 | #栈和排序#

贪心+优先队列

当页数未填满时直接填充，填满之后需要将集合里的数据下一次出现的位置最晚的置换掉

首先关于处理元素下一次出现位置的方法采取倒向扫pos放进ne数组，pos初始化为极大值,当pos[i]==inf时表明接下来不存在该元素

在未填满时更新相同元素的下次出现位置可以不更新而选择直接向优先队列里面插入,同时用k来记录集合里不同的元素个数,当k==n时,每次出现集合内没有的元素都插入到优先队列

在此强调不能用队列的大小代替k,因为遇到相同元素并没有将初始的记录删除而是直接添加进优先队列

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
const int N = 5e4+10;
int n,m,q;
int pos[N],ne[N],a[N];
bool vis[N];
void solve()
{
    memset(pos,0x3f,sizeof pos);
    memset(vis,false,sizeof vis);
    
    for(int i=1;i<=q;++i) cin>>a[i];
    
    for(int i=q;i;--i)
    {
        ne[i] = pos[a[i]];
        pos[a[i]] = i;
    }
    
    priority_queue<PII> qu;
    
    int cnt = 0;
    int k = 0;
    for(int i=1;i<=q;++i)
    {
        if(k<n&&!vis[a[i]])
        {
            k++;
            cnt++;
            vis[a[i]] = 1;
        }
        else if(k==n&&!vis[a[i]])
        {
            cnt++;
            auto t = qu.top();
            qu.pop();
            vis[t.y] = 0;
            vis[a[i]] = 1;
        }
        qu.push({ne[i],a[i]});
    }
    cout<<cnt<<"\n";
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	while(cin>>n>>m>>q)
    {
        solve();
    }
}