题解：P10647 [NordicOI 2023] Ice Cream Machines

前置知识

• 二叉堆（优先队列）
• 贪心算法。

题目大意

有n nn个顾客，k kk台机器，如果没有相应口味的机器，则需要清洗一台机器，在满足所有顾客的需求的条件下，最少清洗的次数。

思路

我们观察题面，通过关键字眼“最少”从而考虑贪心算法。
我们仔细思考，不难想出一种贪心策略：把影响力最小的口味的机器清洗。
这里的影响力指下一次出现最晚的口味，或者说是不会再出现。
那么我们就可以得到贪心算法的具体过程：

1. 场上有相同口味机器，就不需用清洁，直接使用。
2. 场上没有相同口味机器，但又有空余机器，直接将未使用机器清洗。
3. 场上即没有相同口味机器，也没有空余机器，就将影响力最小的口味的机器清洗。

当然，在情况 3 的时候是不能通过枚举查找的，我们需要预处理每个顾客的口味下一次出现的时候，再使用大根堆维护情况 2 与 3 即可。
关于预处理，我们从后向前遍历，用一个nex数组储存每个口味下一次的出现时间，las数组则储存本次口味的时间，在往后遍历到相同口味，就设nex[i]=las[a[i]]，las[a[i]]=i即可。特别地，如果las[a[i]]=0，也就代表当前是最后一次出现该口味，设nex[i]=INT_MAX。

贪心证明与时间复杂度

假设最优解不是清洗影响力最小的机器 A，而是选择了清洗在此之前出现的机器 B，那么中间再次需要使用机器 B 的时候，就需要二次清洗，所以最佳方案是删除 A。所以由此可证明贪心策略是正确的。

关于时间复杂度，我们可以发现，每一种情况的时间复杂度都是O ( log ⁡ n ) O(\log n)O(logn)，那么遍历整个序列，时间复杂度就是O ( n log ⁡ n ) O(n \log n)O(nlogn)。

AC Code

#include<bits/stdc++.h>usingnamespacestd;intn,m,k;inta[500001];intnex[500001];intlas[500001];boolst[500001];priority_queue<pair<int,int>>q;intmain(){cin>>n>>m>>k;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=n;i>=1;i--){if(las[a[i]]==0){nex[i]=INT_MAX;}else{nex[i]=las[a[i]];}las[a[i]]=i;}//预处理每个元素的下一个出现位置intsum=0;for(inti=1;i<=n;i++){if(st[a[i]]!=false){q.push({nex[i],a[i]});}elseif(k!=0){k--;sum++;st[a[i]]=true;q.push({nex[i],a[i]});//cout<<sum<<"\n";}else{while(!q.empty()&&st[q.top().second]==false){q.pop();}//将所有已经处理的那些指令去除st[q.top().second]=false;sum++;st[a[i]]=true;q.push({nex[i],a[i]});//将该机器的重要值加入//cout<<sum<<"\n";}}cout<<sum;}