侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

【贪心】排队打水

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

题目

913. 排队打水 - AcWing题库


nn 个人排队到 11 个水龙头处打水,第 ii 个人装满水桶所需的时间是 tit_i ,请问如何安排他们的打水顺序才能使所有人的等待时间之和最小?

输入格式

第一行包含整数 nn

第二行包含 nn 个整数,其中第 ii 个整数表示第 ii 个人装满水桶所花费的时间 tit_i

输出格式

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

数据范围

1n1051 \le n \le 10^5 ,
1ti1041 \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);
    }
}
0

评论区