NOI 范围内贪心算法的基本模型总结

一棉花糖一 · 2025-01-14 22:31:58 · 算法·理论

NOI 范围内贪心算法的基本模型总结

1. 区间类问题

(1) 区间调度

• 问题描述：从若干区间中选择尽可能多的互不重叠的区间。
• 贪心策略：按结束时间升序排序，每次选择结束时间最早且不冲突的区间。
• 应用：活动安排问题、会议室分配问题。

(2) 区间覆盖

• 问题描述：用尽可能少的区间覆盖一个给定范围 [L, R]。
• 贪心策略：按起点排序，每次选择当前起点能覆盖最远右端点的区间。
• 应用：视频拼接问题。

(3) 区间选点

• 问题描述：在所有区间的交集范围内选择尽可能少的点，使每个区间至少包含一个点。
• 贪心策略：按右端点排序，优先选择当前区间的右端点作为选点。

2. 图论类问题

(1) 最小生成树

• 问题描述：构造图的最小生成树。
• 贪心算法：
  • Kruskal：按边权从小到大排序，使用并查集判断环路。
  • Prim：从任意点出发，逐步加入与当前生成树连通且权值最小的边。

(2) 最短路径（Dijkstra 算法）

• 问题描述：单源最短路径，求某点到其他点的最短距离（非负权图）。
• 贪心策略：每次从未处理的点中选择当前距离最短的点扩展路径。

(3) 最大流中的贪心

• 问题描述：网络流问题中寻找增广路径。
• 贪心策略：在寻找增广路径时，可以优先选择流量更大的路径（非最优，但能加快某些特定场景下的解决速度）。

3. 背包类问题

(1) 分数背包问题

• 问题描述：物品可以分割，求在容量限制下的最大总价值。
• 贪心策略：按单位价值降序选择物品，优先选单位价值最高的物品。

(2) 0-1 背包问题中的贪心优化

• 限制：一般 0-1 背包问题需要动态规划，但可以结合贪心进行剪枝，如通过优先装满高性价比物品的背包快速估计上界以优化搜索。

4. 排序与分配类问题

(1) 任务调度问题

• 问题描述：将若干任务分配给资源或工人，使得完成时间最短或代价最低。
• 贪心策略：按任务优先级排序（如任务时间最短优先），或按资源状态分配给当前负载最小的资源。
• 应用：
  • 多机器任务调度问题。
  • 区间排序模型下的任务分配。

(2) 霍夫曼编码 (NOI 2015)

• 问题描述：基于一组字符及其出现频率构建一棵最优二叉树，使编码总长度最短。
• 贪心策略：每次合并出现频率最小的两棵子树。

5. 贪心选取问题

(1) K 次取数问题

• 问题描述：从一个序列中选出 k 个数，使其和最大或最小。
• 贪心策略：根据问题需求对序列排序，直接选择前 k 个或后 k 个。
• 应用：最大子数组问题、区间选数问题。

(2) 最大/最小代价问题

• 问题描述：求解某种代价最优的问题。
• 贪心策略：每次选择当前对全局影响最小的操作。
• 典型场景：
  • 加油问题：优先选择能到达的最远加油站加油。
  • 优先队列问题：每次合并代价最小的两项（类似霍夫曼编码思想）。

6. 字符串类问题

(1) 字典序最小问题

• 问题描述：从一个字符串中删除若干字符，使得剩余字符字典序最小。
• 贪心策略：保持剩余部分尽可能小且有序，常用单调栈实现。

(2) 最小循环移位

• 问题描述：求一个字符串的所有循环移位中字典序最小的一个。
• 贪心策略：两倍字符串后比较，每次选择局部最优解更新起点。

7. 数列与数组类问题

(1) 单调队列优化

• 问题描述：如滑动窗口最大值问题或队列中最优选择问题。
• 贪心策略：维护一个单调队列，每次根据新元素更新并移除无效元素。

(2) 数列分组问题

• 问题描述：将数列分成若干组使得某种代价最优（如最大组和最小）。
• 贪心策略：按照某种规则排序后分配元素。

8. 数据结构结合贪心

(1) 并查集优化

• 问题描述：多次查询两点连通性或动态添加边。
• 贪心策略：路径压缩和按秩合并是贪心的优化手段，减少查询代价。

(2) 优先队列结合贪心

• 问题描述：动态处理一组数据，求实时最优解。
• 贪心策略：优先队列中每次弹出优先级最高的元素进行操作。
• 应用：任务调度问题、动态最小生成树。

9. 证明贪心算法的正确性

在实际应用中，贪心算法需要满足以下三个条件，确保其解法正确：

1. 贪心选择性质：局部最优解可以构造全局最优解。

   • 示例：区间调度问题中选择结束时间最早的区间，不影响后续选择的最优性。

2. 无后效性：当前选择不影响后续选择的合法性或最优性。

   • 示例：最短路径中，每次选择最短距离点后，不会改变未处理点的最短路径。

3. 子问题最优性：子问题的最优解可以合并成原问题的最优解。

   • 示例：最小生成树中每次加入最小权边不会破坏已选部分的最优性。

10. 排队问题

(1) 排队取水问题

• 问题描述：若干人排队取水，每人需要不同的取水时间，求所有人总等待时间的最小值。
• 贪心策略：按取水时间从小到大排序，先服务耗时短的人。
• 证明：排序后，某人等待时间是前面所有人的取水时间和，排序能最小化总等待时间。

(2) 排队结账问题

• 问题描述：有 k 个结账窗口和若干顾客，求所有顾客完成结账的最短时间。
• 贪心策略：使用最小堆，每次将顾客分配到当前等待时间最短的窗口。

11. 工程调度问题

(1) 最早完成时间优先

• 问题描述：安排 n 个任务在一台机器上完成，每个任务有完成时间，求最小总延迟。
• 贪心策略：按任务完成时间从小到大排序。

(2) 作业工期问题

• 问题描述：安排 n 个作业到两台机器上（流水线），求完成所有作业的最短时间。
• 贪心策略：
  • 若每个作业在机器 A 和 B 的耗时分别为 a 和 b，按 \min(a, b) 升序分配。
  • 先处理耗时较短的作业，减少总工期。

12. 数列与区间问题

(1) 和最大子数组问题

• 问题描述：给定一个数组，求和最大的连续子数组。
• 贪心策略：维护当前子数组和，如果和为负，则重新开始计算。

(2) 数列分组问题

• 问题描述：将数列分为 k 组，最小化最大组和。
• 贪心策略：二分答案，判断是否能在当前最大和限制下完成分组。

13. 资源分配问题

(1) 加油问题

• 问题描述：在一条长路上有若干加油站，初始有有限的油量，求到达终点需要的最少加油次数。
• 贪心策略：每次选择能到达的最远加油站加油。

(2) 最优工人分配问题

• 问题描述：有 n 个工人和 n 项工作，每个工人完成某项工作的代价不同，求最小总代价。
• 贪心策略：使用匈牙利算法或贪心匹配，将工人分配到代价最低的工作上。

14. 几何问题

(1) 最近点对问题

• 问题描述：平面上给定 n 个点，求最近两点的距离。
• 贪心策略：按坐标排序，用分治法优化最近点对的搜索范围。

(2) 凸包问题

• 问题描述：平面上给定 n 个点，求所有点的凸包（最小凸多边形）。
• 贪心策略：使用 Graham 扫描法，按极角排序并维护单调性。

15. 动态维护问题

(1) 动态区间最大值

• 问题描述：在动态增加或删除区间的情况下，实时求最大值或最小值。
• 贪心策略：结合线段树或平衡树，按区间端点动态维护答案。

(2) 动态序列第 k 小值

• 问题描述：在动态插入或删除元素的情况下，实时查询序列的第 k 小值。
• 贪心策略：使用平衡树或二叉索引树动态维护序列。

16. 博弈与胜率问题

(1) 胜率最大化问题

• 问题描述：有 n 场比赛，每场比赛有胜利的概率，求最大胜场数。
• 贪心策略：按概率从大到小选择比赛，优先安排胜率高的比赛。

(2) Nim 博弈

• 问题描述：若干堆石子，两人轮流拿，每次可以从一堆中拿任意数量的石子，求先手是否必胜。
• 贪心策略：计算所有石堆异或和，若不为零则先手必胜。

17. 贪心搜索与剪枝

(1) 八皇后问题

• 问题描述：在 8 \times 8 的棋盘上放置 8 个皇后，互相不能攻击。
• 贪心策略：每次选择当前最优的放置位置，并结合回溯法搜索。

(2) 最短 Hamilton 回路

• 问题描述：在一个图中求经过每个顶点一次的最短回路。
• 贪心策略：每次选择当前路径上最短的边进行扩展。