这一节，我们来解决一个经典的贪心问题：

有 n 个人在一个水龙头前排队接水，假如每个人接水的时间为 ti ，请编程找出这 n 个人排队的一种顺序，使得 n 个人的平均等待时间最小。

初始时，输入输出部分已经写好，我们只需完成剩余的部分。我们的贪心策略是：让接水时间少的人先接水（因为刚开始等的人多）。

1. 首先我们来写排序函数cmp。

在main函数上面写下

bool cmp(Node p1, Node p2) { 


}

2. 我们是按接水时间从小到大排序，接水时间相同时，按编号从小到大排。

在cmp函数里面写下

if (p1.t == p2.t) { 
    return p1.id < p2.id; 
} 
return p1.t < p2.t;

3. 接着，在main函数中调用sort函数来排序。

在main函数中合适的地方写下。

sort(a, a + n, cmp);

4. 最后，我们定义一个变量sum保存总的等待时间，类型为long long。第 i 个人接水的时候（我们下标是从 0 开始的），后面还有 n-i-1 个人在排队，他们要等待(n - i - 1) * a[i].t这么多时间，累加进总等待时间sum里。

在main函数里排序结束后继续写：

long long sum = 0; 
for (int i = 0; i < n; i++) { 
    sum += (n - i - 1) * a[i].t; 
}

5. 点击运行，输入下面的数据查看结果。

6 
18 10 20 14 14 13

#include <algorithm>
#include <cstdio>
using namespace std;

struct Node {
    int id, t;
} a[1005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i].t);
        a[i].id = i + 1;
    }

    for (int i = 0; i < n; i++) {
        printf("%d ", a[i].id);
    }
    printf("\n%.2f\n", (double)sum / n);
    return 0;
}