一、问题背景：为什么要让接水快的人先上？

  假设有 10 个人在水龙头前排队接水，每个人的接水时间分别是 56、12、1、99、1000、234、33、55、99、812 秒。如何安排排队顺序，才能让所有人的平均等待时间最小。

 这里的 “等待时间” 指每个人从排队开始到接水结束的总时间（包含自己的接水时间）。比如 A 先接水（10 秒），B 后接水（20 秒），A 的等待时间是 10 秒，B 的等待时间是 10+20=30 秒，两人平均等待时间为 20 秒。

二、贪心策略的选择：局部最优如何推导全局最优？

要最小化平均等待时间，本质是最小化总等待时间（平均等待时间 = 总等待时间 / 人数，人数固定时，总等待时间最小即平均最小）。

我们来分析总等待时间的构成：

• 第 1 个人的等待时间：T₁（仅自己的接水时间）
• 第 2 个人的等待时间：T₁+T₂
• 第 3 个人的等待时间：T₁+T₂+T₃
• ...
• 第 n 个人的等待时间：T₁+T₂+...+Tₙ

总等待时间 = T₁×n + T₂×(n-1) + T₃×(n-2) + ... + Tₙ×1

从公式可见：接水时间越短的人，被累加的次数越多（比如第 1 个人的时间被加 n 次，第 2 个人被加 n-1 次）。因此，要让总等待时间最小，必须让 “短时间” 被多累加、“长时间” 被少累加 —— 也就是让接水时间短的人排在前面。

这就是贪心策略的核心：每次选择当前接水时间最短的人，优先安排他接水。

三、算法实现与复杂度分析

1. 数据结构设计

我们需要存储每个人的 “接水时间” 和 “原始编号”（题目要求时间相同时，编号小的在前）

2. 排序规则

按 “接水时间升序” 排序，时间相同时按 “编号升序” 排序。

3. 计算总等待时间

遍历排序后的队列，累加每个人的等待时间。

4. 复杂度分析

• 时间复杂度：核心操作是排序，时间复杂度为 O (n log n)（n 为人数），遍历计算总等待时间为 O (n)，整体复杂度由排序主导，即 O (n log n)。
• 空间复杂度：存储 n 个人的信息，为 O (n)。

四、贪心算法的适用场景与注意事项

贪心算法并非万能，它只适用于 “局部最优能推导出全局最优” 的问题。比如本文的 “排队接水”、“合并果子” 等问题，都满足 “贪心选择性质” 和 “最优子结构性质”：

1. 贪心选择性质：每一步的局部最优选择，能导致最终的全局最优。
2. 最优子结构性质：问题的最优解包含子问题的最优解。

如果不满足这两个性质，贪心算法可能会得到错误结果。例如 “0-1 背包” 问题（物品不能分割），贪心策略（选单价最高的）就无法得到最优解，此时需要用动态规划。