染色(贪心+堆)

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

上一篇:java-如何从不完整的类名获取实例对象?


下一篇:Implicit super constructor Object() is undefined for default constructor. Must define an explicit co