P4791 童程同学讲礼貌（入门）

解题思路

1. 读懂题目：n 位同学在一台饮水机前排队接水，每人接水时间不同。题目要求我们找出一种排队顺序，让所有人的"平均等待时间"最小。这里等待时间是指从开始排队到这位同学接完水的总时间，也就是要算上自己打水的时间。

2. 打个比方：就像食堂只有一个打饭窗口，大家都想快点吃上饭。如果有人打饭特别慢还排在队伍最前面，后面所有人都要干等着，非常浪费课间时间。所以当然应该让"接水快"的同学排在前面。

3. 贪心结论：把接水时间从小到大排序，就是最优顺序。因为第一个人接水时后面所有人都在等，他慢一点，被拖累的人就多。

4. 怎么计算总时间：排好队以后，第 1 位同学完成时间是自己的时间 t₁；第 2 位同学要等第 1 位打水，自己再打，完成时间是 t₁+t₂；第 3 位是 t₁+t₂+t₃……也就是第 i 位同学的完成时间等于"前 i 个人接水时间的总和"（前缀和）。把所有人的完成时间加起来，再除以 n，就是平均等待时间。

5. 看例子：样例接水时间排序后是 1,12,33,55,56,99,99,234,812,1000。完成时间依次是 1、13、46、101、157、256、355、589、1401、2401，加起来是 5320，5320÷10=532.00，正好是答案。

6. 边界情况：n=1 时，平均等待时间就是他自己打水的时间；n 最大 1000，每人时间最大 1000，总和可能达到约 5 亿，所以代码里用 long long 来累加，防止整数溢出。

参考代码

// P4791 童程同学讲礼貌：接水时间短的排前面，平均完成时间最小
#include <iostream>
using namespace std;
int waterList[1005];  // 每位同学的接水时间

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> waterList[i];
    // 接水时间升序排序（冒泡排序，时间短的排前面）
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (waterList[j] > waterList[j + 1]) { int temp = waterList[j]; waterList[j] = waterList[j + 1]; waterList[j + 1] = temp; }
    long long totalTime = 0;   // 所有人完成接水的时间总和
    long long prefixSum = 0;   // 排在当前同学前面的同学的总接水时间
    for (int i = 0; i < n; i++) {
        prefixSum += waterList[i];   // 前面的人 + 自己，就是这位同学的完成时间
        totalTime += prefixSum;
    }
    printf("%.2f\n", (double)totalTime / n);
    return 0;
}

复杂度分析

先排序，冒泡排序的时间是 O(n²)，n≤1000，只需要大约一百万次比较，非常快；累加前缀和只扫一遍数组，是 O(n)。空间上只用了一个长度为 1005 的数组，是 O(n)。整体程序运行飞快，轻松通过。