洛谷 P3419 [POI2005]SAM-Toy Cars（贪心、优先队列）

传送门

解题思路

很容易我们可以得出结论，

当地板上的玩具数不足k个时，直接放。
当玩具数量等于k时，从地板上拿走的玩具一定是在地板上玩具中，下一次使用昨晚的那一次。

所以我们用一个优先队列存地板上的玩具，重载运算符，比较next[i]的大小。

接下来想一下怎么求next数组。

可以倒着枚举玩具序列a，用l[i]存储玩具i到目前为止上一次出现的位置，然后每一次next[i]=l[a[i]]，l[a[i]]=i（为了便于比较，当l[a[i]]==0时，代表这是左后一次使用，将next[i]设为无穷大）。

然后具体做法就是枚举玩具序列a：

如果a[i]已经在优先队列里了（用vis表示），期望操作是把a[i]这种玩具的位置更新。可是在优先队列中没有办法更新，于是我们就可以让规定的k++，直接放入新的值即可。为什么是正确的呢？因为先放入的那一次的next值等于i，一定不会作为最大值被pop掉。
如果a[i]没有在队列里，那么又分为两种情况，当元素数量不足k个时，直接push这个值；当元素数量等于k时，把堆顶元素pop掉，然后push这个值，最后ans++。注意pop时要把vis变为0。

AC代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 int n,k,p,a[500005],ne[500005],l[100005],vis[100005],ans;
 6 struct node{
 7     int id;
 8     bool operator <(const node &x)const{
 9         return ne[id]<ne[x.id];
10     }
11 };
12 priority_queue<node> q; 
13 int main()
14 {
15     cin>>n>>k>>p;
16     for(int i=1;i<=p;i++)scanf("%d",&a[i]);
17     for(int i=p;i>=1;i--){
18         if(!l[a[i]]) ne[i]=500001,l[a[i]]=i;
19         else{
20             ne[i]=l[a[i]];
21             l[a[i]]=i;
22         }
23     }
24     for(int i=1;i<=p;i++){
25         node x;
26         if(vis[a[i]]){
27             k++;        
28             vis[a[i]]=1;
29             x.id=i;
30             q.push(x);
31         }else{
32             if(q.size()==k) vis[a[q.top().id]]=0,q.pop();
33             vis[a[i]]=1;
34             x.id=i;
35             q.push(x);
36             ans++; 
37         }
38 
39     }
40     cout<<ans;
41     return 0;
42 }