【贪心】排队打水

题目

913. 排队打水 - AcWing题库

---

有 $n$ 个人排队到 $1$ 个水龙头处打水，第 $i$ 个人装满水桶所需的时间是 $t_i$ ，请问如何安排他们的打水顺序才能使所有人的等待时间之和最小？

输入格式

第一行包含整数 $n$ 。

第二行包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个人装满水桶所花费的时间 $t_i$ 。

输出格式

输出一个整数，表示最小的等待时间之和。

数据范围

$1 \le n \le 10^5$ ,
$1 \le t_i \le 10^4$

输入样例：

7
3 6 1 4 2 5 7

输出样例：

56

解题

方法一：贪心算法 优先队列

思路

贪心策略

优先让所用时间少的人去打水。

为什么是对的

这里不放证明是因为我认为这题用直觉理解起来更加简单易懂。

显然，让办事办得快的人先办事儿所有人需要等的时间和会更少。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        Queue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; ++i) {
            in.nextToken();
            pq.offer((int) in.nval);
        }
        long ans = 0L;
        while (n-- > 0) ans += 1L * pq.poll() * n;
        System.out.println(ans);
    }
}