染色（贪心+堆）

本文主要是介绍染色（贪心+堆），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

tyy 模拟赛 T2，打了 20 分暴力滚粗。

题目内容

.md 文件不在手边，明天再放上来。

解题思路

如果像我一样按题意模拟：枚举染色方案 \(\rightarrow\) 构造序列 \(a\rightarrow\) 比较字典序，那只能得 20 分了。实际上，所谓 \((t_i,i)\) 从大到小排序，就是让多的尽量多，少的尽量少。

初步的贪心是枚举颜色，把能涂成这种颜色的区间全涂掉，剩下的给其它颜色，看起来是 \(\mathcal{O(C^2)}\) 的。正解在此基础上开一个大根的可删除堆，把颜色和其最大长度打包扔进去；然后每次取堆顶，直接输出，枚举每一个这种颜色的区间（之前肯定顺手记录了吧），把它两边的颜色从堆里“删出来”，改一下长度（被当前颜色覆盖了一部分），再放回去。

用两个优先队列、一个 set （或者丧心病狂手写一棵平衡树、一个手写可删除堆都能做到 \(\mathcal{O((c+m)\log(c+m))}\) 的优秀复杂度。

AC 代码

同样不在手边，明天放上。(补充了两个优先队列实现可删除堆的内容)

THE END

这篇关于染色（贪心+堆）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！