How to use Priority Queuing

I solved the D problem of ABC141 with hellish code

I answered AtCoder Beginner Contest 141 last night with hellish code. Problem

Because I don't know the priority queue (Priority Queue), I repeat sort-> pop-> push-> sort ... I have used brain muscle technique, so I reflect on it

Background

A quick explanation for those who do not want to read the problem statement

-** I want to find the price ** to buy all products ** ――Each product has a price ――However, if you have N coupons and use one coupon, ** the price of one product will be half price **

Problems such as

• There is some translation

Basic design in my brain

Isn't it cheaper if you use the most expensive ones until the coupons are used up?

Usage Guide: Suppose you have 3 coupons. There are three products, and the prices are as follows. 100 yen, 75 yen, 40 yen

solution:

1. Use coupons for 100 yen products (100 yen-> 50 yen)
2. Use coupons for 75 yen products (75 yen-> 37 yen)
3. Use coupons for 50 yen products (50 yen-> 25 yen)
4. The total amount of 25 yen, 37 yen, and 40 yen is ** 102 yen **, so output this.

Hell from here

I don't think it was wrong up to the basic design level, Without knowing the priority queue when waking up in code Description that LinkedList + Collections.sort will do its best

Main.java

public static void main(String args[]) {
	FastScanner sc = new FastScanner();
	int n = sc.nextInt();
	int m = sc.nextInt();

	LinkedList<Integer> list = new LinkedList<>();
	for (int i = 0; i < n; i++) {
		list.add(sc.nextInt());
	}

	for (int i = 0; i < m; i++) {
		//Here gorilla
		Collections.sort(list, Collections.reverseOrder());
		list.add(list.pop() / 2);
	}

	long result = 0;
	for (int x : list) {
		result += x;
	}

	System.out.println(result);
}

It probably worked fine as a way to solve the code, Of course, he became TLE and died.

What's over

Needless to say, the part that sorts every time to get the maximum value is useless ... Since sort in java Collection uses modified merge sort, Assuming that the number of products is N and the coupon is M, the processing cost is N log (N) × M times.

PriorityQueue class that can be used in such cases

Resolved by using the priority queue class (PriorityQueue)

How to use PriorityQueue It's very easy to use. Declare the priorityQueue class and set it with the add class, Reference with peak method (get-like behavior), fetch with poll method (pop-like behavior)

Main.java

	public static void main(String[] args) {
		Queue<Integer> q = new PriorityQueue<Integer>();
		q.add(1);
		q.add(2);
		q.add(3);
		q.add(4);
		System.out.println(q.poll());//output:1 q:{2,3,4}
		System.out.println(q.peak());//output:2 q:{2,3,4}
		System.out.println(q.poll());//output:2 q:{3,4}
	}

In the above example, the minimum value of 1 is retrieved. (2,3,4 remain in Queue)

If you want to sort in descending order, set Collections.reverseOrder () in the constructor argument

Main.java

	public static void main(String[] args) {
		Queue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
		q.add(1);
		q.add(2);
		q.add(3);
		q.add(4);
		System.out.println(q.poll());//output:4 q:{3,2,1}
		System.out.println(q.peak());//output:3 q:{3,2,1}
		System.out.println(q.poll());//output:3 q:{2,1}
	}

Submit again using Priority Queuing

Main.java

public static void review(String args[]) {

		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		int m = sc.nextInt();

		Queue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
		for (int i = 0; i < n; i++) {
			q.add(sc.nextInt());
		}

		for (int i = 0; i < m; i++) {
			q.add(q.poll() / 2);
		}

		long result = 0;
		for (int x : q) {
			result += x;
		}

		System.out.println(result);
	}

The result was ** AC ** </ font>, 179ms, which was processed very quickly.