# 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

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();

for (int i = 0; i < n; i++) {
}

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

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>();
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());
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++) {
}

for (int i = 0; i < m; i++) {