侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心】排队打水问题

GabrielxD
2023-04-19 / 0 评论 / 0 点赞 / 113 阅读 / 478 字
温馨提示:
本文最后更新于 2023-04-19,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


nn 个人排队到 rr 个水龙头去打水,他们装满水桶的时间 t1,t2,,tnt_1, t_2, \dots, t_n 为整数且各不相等,应如何安排他们的打水顺序才能使他们总共花费的时间最少?

输入

第一行 n,r(n500,r75)n, r (n \le 500, r \le 75)

第二行为 nn 个人打水所用的时间 Ti(Ti100)T_i (T_i \le 100)

输出

最少的花费时间。

样例输入

3 2
1 2 3

样例输出

7

数据规模和约定

  • 其中 80%80\% 的数据保证 n10n \le 10

解题

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

思路

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

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

代码

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);
    }
}
0
博主关闭了所有页面的评论