【贪心】排队打水问题

题目

试题 算法提高 排队打水问题

---

有 $n$ 个人排队到 $r$ 个水龙头去打水，他们装满水桶的时间 $t_1, t_2, \dots, t_n$ 为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？

输入

第一行 $n, r (n \le 500, r \le 75)$ ；

第二行为 $n$ 个人打水所用的时间 $T_i (T_i \le 100)$ 。

输出

最少的花费时间。

样例输入

3 2
1 2 3

样例输出

7

数据规模和约定

• 其中 $80\%$ 的数据保证 $n \le 10$ ；

解题

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

思路

排队打水的升级版，有 $r$ 个水龙头可以用，那么可以把这 $r$ 个水龙头的使用时间放入小根堆中（初始全是 $0$ ），然后把每个人装满水桶的时间升序排序（ $t$ 数组）。遍历 $t$ 数组，每次取出堆中使用时间最短的水龙头，让当前人去该水龙头处打水。

遍历的过程中水龙头的使用时间累加进答案中，最后得到的就是最少花费时间。

代码

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

public class _排队打水问题 {
    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;
        in.nextToken(); int r = (int) in.nval;
        int[] t = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken(); t[i] = (int) in.nval;
        }
        Arrays.sort(t);
        Queue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < r; ++i) pq.offer(0);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int curr = pq.poll();
            curr += t[i];
            ans += curr;
            pq.offer(curr);
        }
        System.out.println(ans);
    }
}