标签:堆
7 个条目
-
概念 反悔贪心
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。
2026-11-17 -
概念 唯一父状态堆枚举
把隐式状态空间组织成每个非根状态恰有一个父状态的树;父值不大于子值,堆按值弹出即可不重不漏地做第 k 小枚举。
2026-11-17 -
概念 子集第 k 小和
排序正数子集和;用唯一父状态堆枚举,每个状态只生成替换末尾下标和追加下一下标两个后继。
2026-11-17 -
概念 多集合第 k 小和
每个集合选一个数,求和第 k 小;压缩最近一个非首项,按唯一父状态堆枚举,集合按首增量排序。
2026-11-17 -
题目 区间划分
把所有区间分配到最少机器,使同一机器上的区间不重叠;答案等于最大重叠深度,按左端点排序并用小根堆维护结束时间。
2026-11-17 -
题目 最小逾期任务
单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。
2026-11-17 -
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。
2026-11-10