网站建设对企业经营,怎么做倒计时网站,推广app渠道,wordpress腾讯云插件下载优先队列是队列数据结构实现#xff0c;其中根据优先级处理对象#xff0c;在优先队列中#xff0c;添加的对象根据其优先级#xff0c;默认情况下#xff0c;优先级由对象的自然顺序决定的。队列构建时提供的比较器可以覆盖默认优先级。
优先队列就是一个堆#xff0c;…优先队列是队列数据结构实现其中根据优先级处理对象在优先队列中添加的对象根据其优先级默认情况下优先级由对象的自然顺序决定的。队列构建时提供的比较器可以覆盖默认优先级。
优先队列就是一个堆它可以维护一个集合的最大值或最小值可以在很优秀的时间复杂度log级别内进行查询插入push和删除pop.
例题
问题描述 小雷拿到了一个数组他计算了一下数组的和感觉和也太大了所以他准备对数组中的每个元素进行取余操作让数组的和变得小一点。
具体来说给定一个数组 a 共有 q 次操作每次操作给定一个值 x 对数组的每个元素对 x 进行一次取模输出每次操作后数组所有元素的和。
输入格式
第一行有两个整数n,q 代表数组 a 的元素个数和操作个数。
第二行输入 n 个元素代表数组 a 。
第三行输入 q 个元素代表 q 次操作。
输出格式
输出仅一行包含 q 个由空格分开的整数第 i 个整数代表第 qi 次操作后的结果。
样例输入
5 3
1 2 3 4 5
4 2 1样例输出 7 3 0说明 初始数组为 [1,2,3,4,5] 和为 15 。
进行第一次 x 为 4 的取模操作后数组变为 [1,2,3,0,1] 和为 7 。
进行第二次 x 为 2 的取模操作后数组变为 [1,0,1,0,1] 和为 3 。
进行第三次 x 为 1 的取模操作后数组变为 [0,0,0,0,0] 和为 0。 构建数值从大到小的优先序列 每次比较对头和x的大小关系如果队头大于x把对头弹出来将队头对x取模的值压入队列中。 代码
package dui;
import java.util.*;
public class chapter1 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scannew Scanner(System.in);int nscan.nextInt();int qscan.nextInt();long sum0;PriorityQueueInteger queuenew PriorityQueue((o1,o2)-o2-o1);for(int i0;in;i) {int xscan.nextInt();queue.add(x);sumx;}while(q--0) {//q次操作int kscan.nextInt();while(!queue.isEmpty()queue.peek()k) {//判断队列是否为空以及对头中的元素大于我们当前要取余的值int xqueue.poll();//弹出一直弹出比k大的数sum-x;queue.add(x%k);//对k取余后的值添加到队列中sumx%k;}System.out.print(sum );//每次需要输出sum}}}
