P4658 等候时间（基础）

解题思路

第一步，读懂题目。 港口每次只能进一艘船卸货，每艘船都要等它前面所有船都卸完货才能开始卸，我们的任务是安排进港顺序，让所有船等候时间的总和最小。

第二步，先想清楚"等候时间"怎么算。 假设有三艘船，卸货时间分别是 5、1、2。如果按 5、1、2 的顺序进港：第一艘船不用等（等候 0），第二艘船要等第一艘的 5 分钟，第三艘船要等第一艘和第二艘共 5+1=6 分钟，总和是 0+5+6=11。如果按 1、2、5 的顺序进港：等候是 0+1+(1+2)=4。显然，让卸货快的船先卸货，总等候时间更小。

第三步，定出贪心策略。 把卸货时间从小到大排序。为什么这样是最优的？因为排在越前面的船，它的卸货时间会被越多后面的船反复等待，所以越快的船越应该排前面，越慢的船越应该排后面。排在最前面的船，它的卸货时间会被后面 n-1 艘船各等待一次；而排在最后面的船，它的卸货时间不会被任何船等待，所以最慢的船要放在最后。

第四步，用前缀和累加答案。 用一个变量 prevSum 记录"到目前为止，前面所有船卸货时间的总和"。依次处理排好序的每艘船：先把答案加上 prevSum（这艘船要等前面 prevSum 的时间），再把 prevSum 加上这艘船的卸货时间。等 n 艘船都处理完，答案就是最小的总等候时间。注意总等候时间可能很大，要用 long long 保存。

第五步，体会贪心算法的思想。 每一步都做出当前看起来最优的选择（让最快、最轻的先上），这些选择组合起来就是全局最优解，这就是"贪心算法"的典型思路：局部最优的叠加带来全局最优。

参考代码

// P4658 等候时间：卸货时间短的船先卸货，总等候时间最小
#include <iostream>
#include <algorithm>
using namespace std;

int unloadTime[100005];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> unloadTime[i];
    sort(unloadTime, unloadTime + n); // 从小到大排：卸货快的船先卸货，慢的放最后
    long long answer = 0, prevSum = 0;
    // 每艘船的等候时间 = 它前面所有船卸货时间的总和（累积等待）
    for (int i = 0; i < n; i++) {
        answer += prevSum;          // 第 i 艘船要等前面 prevSum 的时间
        prevSum += unloadTime[i];   // 更新前缀和
    }
    cout << answer << endl;
    return 0;
}

复杂度分析

排序 O(n log n)，一趟累加 O(n)，总时间 O(n log n)。即使 n 到 10 万，也能在一秒内完成。空间上只用存下所有卸货时间，O(n)。