寒光博客

[模拟]普及组 NOIP2010接水问题 及优先队列优化
题目 学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。 现在有n名同...
扫描右侧二维码阅读全文
10
2020/08

[模拟]普及组 NOIP2010接水问题 及优先队列优化

题目

学校里有一个水房,水房里一共装有m个龙头可供同学们打开水,每个龙头每秒钟的供水量相等,均为1。

现在有n名同学准备接水,他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n编号,i号同学的接水量为wi。接水开始时,1到m号同学各占一个水龙头,并同时打开水龙头接水。当其中某名同学j完成其接水量要求wj 后,下一名排队等候接水的同学k马上接替j同学的位置开始接水。这个换人的过程是瞬间完成的,且没有任何水的浪费。即j同学第x秒结束时完成接水, 则k同学第x+1秒立刻开始接水。 若当前接水人数n不足m,则只有n个龙头供水,其它m−n个龙头关闭。

现在给出n名同学的接水量,按照上述接水规则,问所有同学都接完水需要多少秒。

输入描述:

第1行2个整数n和m,用一个空格隔开,分别表示接水人数和龙头个数。
第2行n个整数w1、w2、……、wn,每两个整数之间用一个空格隔开,wi表示i号同学的接水量。

输出描述:

输出只有一行,1个整数,表示接水所需的总时间。

5 3 
4 4 1 2 1

思路

所有人排成一个队列,依次去前往出水量最小的水龙头接水。

代码

用优先队列(小根堆)来对求最小值 优化。

暴力模拟

import java.util.Scanner;

import static java.lang.Math.max;
import static java.lang.Math.random;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();//人数
        int m = cin.nextInt();//水龙头数
        int[] q = new int[n];//人
        int[] w = new int[m];//水
        for (int i = 0; i < n; i++) {
            q[i] = cin.nextInt();
        }
        int time = 0;
        //模拟接水的过程
        for (int i = 0; i < n; i++) {//每个人
            int t = 0;//那一个水龙头结束时间最小
            for (int j = 0; j < m; j++) {
                if (w[j] < w[t]) {
                    t = j;
                }
            }
            w[t] += q[i];
        }
        for (int i = 0; i < m; i++) time = max(time, w[i]);
        System.out.println(time);
    }
}

使用优先队列优化最小值求最大值

PriorityQueue
PriorityQueue 一个基于优先级的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。
PriorityQueue 队列的头指排序规则最小那哥元素。如果多个元素都是最小值则随机选一个。
PriorityQueue 是一个无界队列,但是初始的容量(实际是一个Object[]),随着不断向优先级队列添加元素,其容量会自动扩容,无需指定容量增加策略的细节。

再更新最小的出水口的时候 只需要取出头部即可
最后求最大出水量的时候 弹出所有元素,最后一个就是ans

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();//队头最小元素
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();//人数
        int m = cin.nextInt();//水龙头数
        int[] q = new int[n];//人
        int time = 0;

        for (int i = 0; i < m; i++) //初始化 优先队列
            heap.add(0);
        for (int i = 0; i < n; i++) {//每个接水的数据输入
            q[i] = cin.nextInt();
        }

        //模拟接水的过程
        for (int i = 0; i < n; i++) {//一次对每个人接水
            int t = heap.peek();//取出最小
            heap.poll();//删除
            heap.add(t + q[i]);//更新
        }
        while (!heap.isEmpty()) {//取出最后一个值 最大值
            time=heap.poll();
        }

        System.out.println(time);
    }
}
本文作者:Author:     文章标题:[模拟]普及组 NOIP2010接水问题 及优先队列优化
本文地址:https://dxoca.cn/Algorithm/380.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 10th, 2020 at 11:34 am
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

2 comments

  1. hkea Google Chrome 78.0.3904.108 Windows 7 中国 广西 桂林

    最低仅要0.2元一单,收发货地址匹配全国任意地区,快递代发 快递单号网www.kuaidi5u.com

  2. Escher Google Chrome 84.0.4147.125 Windows 10 中国 贵州

    扑捉Java大佬一枚