题解 P3419 【[POI2005]SAM-Toy Cars】
oscar
2017-09-09 11:52:13
【POI补全计划#3 POI2005 SAM】
这题貌似是个经典贪心诶
每次选择将来最晚用到的玩具放上柜子就好了
**本做法根本不需要手写堆**
我们先预处理一个NEXT数组，
NEXT[i]=j 代表与第i个位置的数相同的数下一次出现在第j个位置
接下来使用priority\_queue
比较函数自己写一个
```cpp
struct cmp
{
inline bool operator()(const int &x,const int &y)
{
return NEXT[x]<NEXT[y];
}
};
```
注意传给priority\_queue的模板参数必须要是一个class/struct
然后这么声明priority\_queue
```cpp
priority_queue<int,vector<int>,cmp> pq;
```
接下来就是一个模拟的过程，开一个数组记录当前哪些玩具在地上
每次发现一个要玩的玩具不在地上且地上的玩具满的时候（相当于优先队列大小恰好等于 $ k $ ）把优先队列中将要最后使用的玩具放到柜子上，再把柜子上的玩具拿下来
**但是这里有点问题：**
**如果某个玩具在地上的话是不会更新优先队列中的时间信息的**
**观察到如果一个玩具被使用过后就再也不会成为优先队列的top**
**所以我们每次发现玩具在地上时把地板大小（ $ k $ ）+1就好了**
考虑到我可能讲得不清楚，我还是贴一下代码吧：
```cpp
#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;
}
```