CSP-J 复赛算法贪心算法

文章目录

前言
贪心算法
- 贪心算法在生活中的例子
- - 贪心算法的基本思路：
  - 贪心算法适用问题：
  - 贪心算法适用问题示例：
  - 贪心算法流程图
排队接水问题
- 问题分析
- - 算法步骤
  - 贪心算法证明
  - 代码实现
  - 代码解释：
  - 测试用例
  - 结论
总结

前言

在算法竞赛中，贪心算法因其简洁和高效的特点成为解决问题的重要工具之一。它通过在每个阶段选择当前最优解（局部最优解），期望最终能导向全局最优解。在实际应用中，贪心算法适用于某些特定问题，例如最小生成树、活动安排、背包问题等。在CSP-J复赛中，贪心算法也经常出现在需要快速做出最优选择的场景中。

贪心算法的核心思想在于每次做出局部最优选择而不考虑全局问题的细节。因此，贪心算法的正确性依赖于问题本身是否具备“贪心选择性质”和“最优子结构”这两个关键性质。如果一个问题符合这两个条件，贪心算法就能很好地解决该问题并保证全局最优解。

通过研究贪心算法，我们不仅可以提升解决特定类型问题的能力，还能加深对算法设计策略的理解，为后续的高级竞赛题型打下坚实的基础。在本文中，我们将介绍贪心算法在CSP-J复赛中的常见应用场景，并通过实际的例题讲解如何利用贪心策略快速、准确地解题。

贪心算法

贪心算法是一种在每一步选择中，始终做出当前最优解的策略，以期望通过一系列局部最优解达到全局最优结果。它不追溯或修正以前的决策，一旦做出选择，不能再改变，因此贪心算法只能用于某些特定的问题类型。

贪心算法在生活中的例子

找零问题：假设你需要找零，面额有1元、5元、10元等，贪心算法的做法是优先用最大面额的硬币，以最少数量的硬币完成找零。
时间管理：例如安排一天的任务时间，贪心策略是每次选择耗时最短的任务先做完，能快速完成更多的任务。
活动选择问题：在有限的时间内，如何选择尽可能多的活动，例如安排会议，每次总是选择最早结束的活动。

贪心算法的基本思路：

问题分解：将问题分解为一系列子问题。
局部最优选择：在每一步选择中，始终做出当前看似最优的决策。
不可回溯：一旦做出选择，不能回退或更改之前的决策。
合并解：通过一系列局部最优解合并成全局解。

贪心算法适用问题：

贪心算法不能保证所有问题的全局最优解，因此它适用于特定类型的问题，通常满足以下两个条件：

贪心选择性质：局部最优解能导向全局最优解，即做出的局部决策不会影响全局最优解。
最优子结构性质：问题的全局最优解能够通过其子问题的最优解组合而成。

贪心算法适用问题示例：

最小生成树问题：用贪心算法的Kruskal或Prim算法求图的最小生成树。
最短路径问题：Dijkstra算法就是一种基于贪心策略的最短路径算法。
背包问题（0-1 背包的贪心版本）：每次选择性价比最高的物品放入背包，直到背包装满。

贪心算法流程图

graph TD;A(开始) --> B(分解问题);B --> C{是否可以直接做选择?};C -- 是 --> D(选择当前最优解);D --> E(更新问题);E --> C;C -- 否 --> F(合并局部解);F --> G(得出全局解);G --> H(结束);

适用问题：

贪心算法适用于那些可以通过一系列局部最优决策得到全局最优解的问题，比如活动选择问题、图中的最小生成树问题等。

这个问题是一个典型的 贪心算法 问题，目标是通过调整排队顺序，使得所有人的平均等待时间最小。我们可以通过分析每个人的接水时间来决定如何安排他们的顺序。

排队接水问题

问题分析

定义等待时间：
假设有 ( n ) 个人排队，第 ( i ) 个人接水需要的时间为 ( T_i )。
当所有人按某种顺序排队时，每个人的等待时间是所有排在他前面的人接水时间之和。
比如：
- 第一个人不需要等待，等待时间为 0。
- 第二个人需要等待第一个人接水的时间，等待时间为 ( T_1 )。
- 第三个人需要等待前两个人接水的时间，等待时间为 ( T_1 + T_2 )。
- 以此类推，第 ( i ) 个人的等待时间为前 ( i-1 ) 个人接水时间的总和。
优化思路：
我们的目标是让所有人的平均等待时间最小。
显然，接水时间越短的人应该越早排队，因为这样能减少后面的人等待的时间。
贪心策略：按照接水时间 ( T_i ) 从小到大排序排队。
平均等待时间计算：
总等待时间是所有人的等待时间之和，平均等待时间是总等待时间除以人数 ( n )。

算法步骤

对每个人的接水时间排序，使得接水时间短的人排在前面。
计算每个人的等待时间，即每个人前面所有人的接水时间之和。
计算平均等待时间。

贪心算法证明

根据贪心选择的性质，如果我们按照接水时间从小到大排序，就能在每一步都保证局部最优解，并最终获得全局最优解。这个问题满足贪心算法的两个条件：

贪心选择性质：在每一步选择中，安排时间短的人先接水能够减少后续人等待的总时间。
最优子结构：如果我们对前 ( i ) 个人的排队顺序是最优的，那么加入第 ( i+1 ) 个人时，仍然可以通过选择最短时间来保持最优解。

代码实现

下面是这个问题的 Python 实现：

#include <iostream>
#include <vector>
#include <algorithm> // 用于 sort 函数using namespace std;// 计算最小平均等待时间
double minAvgWaitTime(vector<int>& T) {int n = T.size();// 1. 将接水时间按从小到大排序sort(T.begin(), T.end());// 2. 计算总等待时间int totalWaitTime = 0;int currentWaitTime = 0;for (int i = 0; i < n; ++i) {totalWaitTime += currentWaitTime;currentWaitTime += T[i];}// 3. 计算平均等待时间double avgWaitTime = static_cast<double>(totalWaitTime) / n;return avgWaitTime;
}int main() {// 测试用例：接水时间vector<int> T = {3, 1, 4, 3, 2};// 计算最小平均等待时间double avgTime = minAvgWaitTime(T);// 输出结果cout << "最小平均等待时间为: " << avgTime << endl;return 0;
}

代码解释：

输入：
T 是一个列表，存储了每个人的接水时间。
排序：
首先将接水时间从小到大排序，这样可以使得等待时间最短。
计算等待时间：
使用两个变量 total_wait_time 和 current_wait_time。current_wait_time 记录当前人接水之前的所有等待时间，并累加到 total_wait_time。
输出：
返回所有人的平均等待时间。

测试用例

对于 T = [3, 1, 4, 3, 2]：

排序后接水时间为：[1, 2, 3, 3, 4]
每个人的等待时间：
- 第一个人等待 0 分钟
- 第二个人等待 1 分钟
- 第三个人等待 1 + 2 = 3 分钟
- 第四个人等待 1 + 2 + 3 = 6 分钟
- 第五个人等待 1 + 2 + 3 + 3 = 9 分钟
总等待时间为：0 + 1 + 3 + 6 + 9 = 19
平均等待时间为：19 / 5 = 3.8

因此，输出的最小平均等待时间为 3.8。