标签:贪心
32 个条目
-
概念 反悔贪心
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。
2026-11-17 -
概念 贪心选择模型
选择型贪心的集合模型:按代价非减序加入可行元素;安全选择与交换论证给出正确性条件,拟阵是充分条件。
2026-11-17 -
概念 最大子段和
求数组中和最大的连续非空子段;前缀和最小值与 Kadane 扫描给出两种等价视角。
2026-11-17 -
构造长度 N^2 的序列,每个 i 出现 N 次且第 i 个 i 在 x_i;按 x_i 排序后从左右两端贪心填数。
2026-11-17 -
树上拓扑序最小逆序对;按块中 0/1 数量比贪心,把最优块并入父块,优先队列加并查集维护。
2026-11-17 -
把 2N 个数配成 N 对,最小化 (x+y) mod M 的最大值;排序后二分分段,段内首尾配对。
2026-11-17 -
在加减表达式中任意加括号使结果最大;只需要考虑减号后的括号,括号层数不超过两层,三状态 DP。
2026-11-17 -
把行列建成二分图,卡片是边;可行选择等价于伪森林,按权值降序用带环标记的并查集贪心求最大权伪森林。
2026-11-17 -
硬币面值都是 2 的非负整数次幂;按面值从大到小取硬币,最小化凑出每个询问金额的硬币数。
2026-11-17 -
移动糖果等价于给前缀和加一或减一;枚举总和的质因子 k,把每个前缀和调整到最近的 k 的倍数。
2026-11-17 -
区间平均化操作;答案是前缀和点集下凸壳的斜率,用单调栈维护分段平均,交叉相乘避免浮点。
2026-11-17 -
只在检查日充钱;维护余额可达区间,区间全负时强制充一次,否则抬高下界,得到最少充钱次数。
2026-11-17 -
题目 分组选择
每组至多选一个带权元素,按权值降序加入;是贪心选择模型的最小入门题,也是划分拟阵的实例。
2026-11-17 -
题目 区间覆盖
用最少的给定区间覆盖目标区间;按左端点排序,每次选择能接上且右端点最远的区间。
2026-11-17 -
题目 区间划分
把所有区间分配到最少机器,使同一机器上的区间不重叠;答案等于最大重叠深度,按左端点排序并用小根堆维护结束时间。
2026-11-17 -
题目 区间点覆盖
选择最少的点,使每个区间至少包含一个点;按右端点排序,在未覆盖区间的右端点放点。
2026-11-17 -
题目 区间调度
选择最多两两不相交的区间;按右端点升序,能选就选,交换论证给出最优性。
2026-11-17 -
题目 国王游戏
重排大臣顺序,最小化最大奖励;按左右手数字乘积升序排序,高精度计算。
2026-11-17 -
题目 排队接水
按接水时间从小到大排序,使总等待时间最小;相同时间按编号升序。
2026-11-17 -
题目 消防局的设立
树上选最少的点,使每个点到某个选中点的距离不超过 2;按深度从大到小,在未覆盖点的爷爷处放消防站。
2026-11-17 -
题目 随机数生成器
生成棋盘排列后,按数值从小到大尝试选格;维护每行可选列区间,得到排序后字典序最小的右上/右下路径序列。
2026-11-17 -
题目 最大 K 子段和
支持区间覆盖和区间内选至多 k 个不相交子段;线段树维护最大/最小子段和,反复取最大子段并取反。
2026-11-17 -
题目 最小逾期任务
单机非抢先调度中最小化逾期任务数;等价于选最大可准时子集,Moore–Hodgson 用最大堆反悔最长任务。
2026-11-17 -
题目 多机区间调度
有 m 个学生和 n 个任务区间,每个任务至多一人完成,最大化可完成任务数;按结束时间排序并分配给最晚可接的学生。
2026-11-17 -
题目 单位时间任务调度
每个任务耗时为 1、有截止期和利润,选择可准时完成的任务使利润最大;按利润降序用并查集找最晚空位。
2026-11-17 -
概念 贪心决策模型
把贪心抽象为确定性序贯决策:状态、动作、代价与安全选择;选择型和合并型都落入同一框架。
2026-11-15 -
概念 贪心合并模型
反复合并两个最小权对象,代价为两权之和;用二叉合并树与交换论证证明最优,是 Huffman 合并的抽象。
2026-11-15 -
概念 序贪心条件
在可用集合上按优先级取极值;静态全序对应排序贪心,后继关系对应最佳优先与多路归并。
2026-11-15 -
概念 Borůvka 算法
每一轮让每个连通块选出一条最小出边并同时合并,O(log n) 轮得到最小生成树。
2026-11-15 -
概念 Kruskal 算法
把边按权值排序,用并查集依次加入不成环的边,最终得到最小生成树。
2026-11-15 -
概念 Prim 算法
从单个点出发,每次把连接已选集合的最小边加入,逐步扩展出最小生成树。
2026-11-15 -
构造 m 条边的连通简单图,边权为 a_u a_v;先求 MST,再用排序后的点权多路归并选剩余最小边。
2026-11-10