题解 P3419 【[POI2005]SAM-Toy Cars】

· · 题解

【POI补全计划#3 POI2005 SAM】

这题貌似是个经典贪心诶

每次选择将来最晚用到的玩具放上柜子就好了

本做法根本不需要手写堆

我们先预处理一个NEXT数组，

NEXT[i]=j 代表与第i个位置的数相同的数下一次出现在第j个位置

接下来使用priority_queue

比较函数自己写一个

struct cmp
{
    inline bool operator()(const int &x,const int &y)
    {
        return NEXT[x]<NEXT[y];
    }
};

注意传给priority_queue的模板参数必须要是一个class/struct

然后这么声明priority_queue

priority_queue<int,vector<int>,cmp> pq;

接下来就是一个模拟的过程，开一个数组记录当前哪些玩具在地上

每次发现一个要玩的玩具不在地上且地上的玩具满的时候（相当于优先队列大小恰好等于 k ）把优先队列中将要最后使用的玩具放到柜子上，再把柜子上的玩具拿下来

但是这里有点问题：

如果某个玩具在地上的话是不会更新优先队列中的时间信息的

观察到如果一个玩具被使用过后就再也不会成为优先队列的top

所以我们每次发现玩具在地上时把地板大小（ k ）+1就好了

考虑到我可能讲得不清楚，我还是贴一下代码吧：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=100010,MAXM=500010;
queue<int> q[MAXN];
int NEXT[MAXM];
int a[MAXM];
int n,k,m;
struct cmp
{
    inline bool operator()(const int &x,const int &y)
    {
        return NEXT[x]<NEXT[y];
    }
};
priority_queue<int,vector<int>,cmp> pq;
int inq[MAXN],ans;
int main()
{
    scanf("%d%d%d",&n,&k,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&a[i]);
        q[a[i]].push(i);
    }
    for(int i=1;i<=m;i++)
    {
        q[a[i]].pop();
        if(q[a[i]].empty())NEXT[i]=m+1;
        else NEXT[i]=q[a[i]].front();
    }
    for(int i=1;i<=m;i++)
    {
        if(!inq[a[i]])
        {
            if(pq.size()==k)
            {
                inq[a[pq.top()]]=0;
                pq.pop();
            }
            pq.push(i);
            ++ans;
            inq[a[i]]=1;
        }
        else
        {
            ++k;
            pq.push(i);
        }
    }
    printf("%d\n",ans);
    return 0;
}