题目描述： 假设n个人不约而同（即同一个时刻，可以假定为0时刻）到达取水点。取水点同一时间只能供一个人取水。输入这n个人取水所需的时间，为t1, t2, …, tn，其中ti为正整数。由于这n个人是同时到达取水点的，而且这n个人都很谦让，因此我们可以随意安排他们的接水顺序。现在要求这n个人接水的一种先后顺序，使得这n个人的平均等待时间最小。事实上，总等待时间最小一定就意味着平均等待时间最小，所以本题要求输出最小的总等待时间。 注意：等待时间定义为一个取水人从到达取水点的时刻算起，到轮到他接水的时刻的这段时间，不包括他接水所花的时间。 输入描述： 输入数据占2行，第一行为正整数n，2≤n≤100，表示人数。第2行有n个正整数，表示这n个人接水所需的时间。 输出描述： 输出占一行，为最小的总等待时间。 样例输入1： 样例输出1： 5 5 3 10 4 9 43 样例输入2： 样例输出2： 5 6 6 6 6 6 60用c++编写代码

以下是C++的实现代码：

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    int n, t;
    cin >> n;
    priority_queue<int, vector<int>, greater<int>> pq; // 小根堆
    for (int i = 0; i < n; i++) {
        cin >> t;
        pq.push(t);
    }
    int ans = 0, cur = 0;
    while (!pq.empty()) {
        int t = pq.top();
        pq.pop();
        cur += t;
        ans += cur;
    }
    cout << ans << endl;
    return 0;
}

首先读入n和每个人的取水时间，然后将每个人的取水时间加入到一个小根堆中。每次从小根堆中取出取水时间最短的人，累加上他的等待时间，并将其加入到总等待时间中。然后重复执行这个过程，直到小根堆中的所有人都被处理完毕。最后输出总等待时间即可。

需要注意的是，我们选择了使用小根堆来实现这个贪心算法，因为我们希望先处理取水时间短的人，这样可以减少后面人的等待时间。使用小根堆可以保证每次取出的人都是取水时间最短的，从而使得算法正确性得到保证。

相关问题

题目描述： 假设n个人不约而同（即同一个时刻，可以假定为0时刻）到达取水点。取水点同一时间只能供一个人取水。输入这n个人取水所需的时间，为t1, t2, …, tn，其中ti为正整数。由于这n个人是同时到达取水点的，而且这n个人都很谦让，因此我们可以随意安排他们的接水顺序。现在要求这n个人接水的一种先后顺序，使得这n个人的平均等待时间最小。事实上，总等待时间最小一定就意味着平均等待时间最小，所以本题要求输出最小的总等待时间。 注意：等待时间定义为一个取水人从到达取水点的时刻算起，到轮到他接水的时刻的这段时间，不包括他接水所花的时间。 输入描述： 输入数据占2行，第一行为正整数n，2≤n≤100，表示人数。第2行有n个正整数，表示这n个人接水所需的时间。 输出描述： 输出占一行，为最小的总等待时间。 样例输入1： 样例输出1： 5 5 3 10 4 9 43 样例输入2： 样例输出2： 5 6 6 6 6 6 60

这是一个经典的贪心算法问题，也可以用排序算法来解决。下面是一种基于优先队列的贪心算法的思路：

1.将所有人的取水时间按照从小到大的顺序加入到一个优先队列中。

2.从优先队列中依次取出每个人的取水时间，将其累加到等待时间中，并计算当前的总等待时间。

3.将当前的总等待时间加入到答案中，并将其作为下一次取水的起点。

4.重复步骤2和步骤3，直到所有人的取水时间都被处理完毕。

最终得到的答案就是最小的总等待时间。

下面是一个基于C++ STL中的优先队列实现的代码：

假设n个人不约而同（即同一个时刻，可以假定为0时刻）到达取水点。取水点同一时间只能供一个人取水。输入这n个人取水所需的时间，为t1, t2, …, tn，其中ti为正整数。由于这n个人是同时到达取水点的，而且这n个人都很谦让，因此我们可以随意安排他们的接水顺序。现在要求这n个人接水的一种先后顺序，使得这n个人的平均等待时间最小。事实上，总等待时间最小一定就意味着平均等待时间最小，所以本题要求输出最小的总等待时间。 注意：等待时间定义为一个取水人从到达取水点的时刻算起，到轮到他接水的时刻的这段时间，不包括他接水所花的时间。

这是一个经典的贪心问题，可以使用贪心算法来解决。我们可以将所有人的取水时间从小到大排序，然后按照这个顺序一个一个地让他们取水。这样做的原因是因为如果等待时间长的人先取水，会导致后面的人等待时间更长，而如果等待时间短的人先取水，后面的人等待时间会更短。

具体地，我们可以使用一个变量curTime来记录当前的时间，一开始curTime为0。然后对所有人的取水时间排序，按顺序遍历每个人，每次更新curTime为当前时间和上一个人的取水完成时间中的较大值，然后将当前人的等待时间加入总等待时间中，并将curTime更新为当前人取水完成的时间。最后输出总等待时间即可。

以下是对应的Python代码实现：

n = int(input())
times = list(map(int, input().split()))

times.sort()
totalTime = 0
curTime = 0

for i in range(n):
    curTime = max(curTime, times[i-1]) if i > 0 else 0
    totalTime += curTime - times[i]
    curTime += times[i]

print(totalTime)