JSOI2010 缓存交换

题目链接：戳我

考虑一个贪心——就是每次我们都选择队列里面之后最晚加入的元素弹出。

维护一个nxt数组就行了。

特判一下之后不会再加入的元素。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

#define MAXN 200010

using namespace std;

int n,m,ans,cnt;

int a[MAXN],pre[MAXN],nxt[MAXN],done[MAXN],last[MAXN];

priority_queue<int,vector<int>,less<int> >q;

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("ce.in","r",stdin);

    #endif

    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++) scanf("%d",&a[i]);

    memcpy(pre,a,sizeof(a));

    sort(&pre[1],&pre[n+1]);

    int tot=unique(&pre[1],&pre[n+1])-pre-1;

    for(int i=1;i<=n;i++) a[i]=lower_bound(&pre[1],&pre[tot+1],a[i])-pre;

    for(int i=1;i<=n;i++) nxt[last[a[i]]]=i,last[a[i]]=i;

    for(int i=1;i<=n;i++)

    {

        if(last[a[i]]) nxt[last[a[i]]]=i,last[a[i]]=i;

        else last[a[i]]=i;

    }

    for(int i=1;i<=tot;i++) nxt[last[i]]=i+n,a[i+n]=i;

    for(int i=1;i<=n;i++)

    {

        while(!q.empty()&&done[a[q.top()]]==0) q.pop();

        if(done[a[i]]==1) {q.push(nxt[i]);continue;}

        if(cnt>=m)

        {

            done[a[q.top()]]=0;

            q.pop();

        }

        else cnt++;

        ans++;

        done[a[i]]=1;

        q.push(nxt[i]);

    }

    printf("%d\n",ans);

    return 0;

}