前置知识二叉堆优先队列贪心算法。题目大意有n nn个顾客k kk台机器如果没有相应口味的机器则需要清洗一台机器在满足所有顾客的需求的条件下最少清洗的次数。思路我们观察题面通过关键字眼“最少”从而考虑贪心算法。我们仔细思考不难想出一种贪心策略把影响力最小的口味的机器清洗。这里的影响力指下一次出现最晚的口味或者说是不会再出现。那么我们就可以得到贪心算法的具体过程场上有相同口味机器就不需用清洁直接使用。场上没有相同口味机器但又有空余机器直接将未使用机器清洗。场上即没有相同口味机器也没有空余机器就将影响力最小的口味的机器清洗。当然在情况 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#includebits/stdc.husingnamespacestd;intn,m,k;inta[500001];intnex[500001];intlas[500001];boolst[500001];priority_queuepairint,intq;intmain(){cinnmk;for(inti1;in;i){cina[i];}for(intin;i1;i--){if(las[a[i]]0){nex[i]INT_MAX;}else{nex[i]las[a[i]];}las[a[i]]i;}//预处理每个元素的下一个出现位置intsum0;for(inti1;in;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]});//coutsum\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]});//将该机器的重要值加入//coutsum\n;}}coutsum;}