假设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)

相关问题

题目描述： 假设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中的优先队列实现的代码：

红河学院又称国门大学，是在滇南的一颗璀璨明珠。学校里的“有名潭”是打卡夕阳，出片的好去处。 这天你和你的朋友一个在红院有名潭，一个在蒙自南湖的先锋书店，你们不约而同的看向天空，那里一定 有相同的云吧？ 很神奇的是，今天的云彩都特别像一个个的数字。 你和你同学分别记录下了你们看见的云的形状。你们觉得，只要两人看见了同一朵云，这是非常有意思的 事情。请你帮他们计算他们今天的默契值。 输入 输入：3行数据，第一行两个数字n和m，分别表示你和你朋友看见的云朵的数量。 第2行 n个数据，表示你看到的云朵的形状 第3行 m个数据，表示你朋友看到的云朵的形状 输出 输出： 一行，你们两个的默契值。 样例 输入复制 4 6 1 9 8 6 6 2 9 7 5 4 输出复制 15 提示 样例说明： 你看见了4朵云彩，分别是1 9 8 6，你朋友看见了6朵云彩，分别是6 2 9 7 5 4 你们同时看见了6和9 两朵云，所以你们的默契度是15. 数据范围：n和m均为0到100，云朵的形状为0-100 用C++写出代码

#include <iostream>
#include <unordered_set>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    unordered_set<int> s;
    int num;
    for (int i = 0; i < n; i++) {
        cin >> num;
        s.insert(num);
    }
    int res = 0;
    for (int i = 0; i < m; i++) {
        cin >> num;
        if (s.count(num)) {
            res += num;
        }
    }
    cout << res << endl;
    return 0;
}