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

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.

Recommended Posts

How to use Priority Queuing
How to use Map
How to use rbenv
How to use letter_opener_web
How to use with_option
How to use fields_for
How to use java.util.logging
How to use map
How to use collection_select
How to use Twitter4J
How to use active_hash! !!
How to use MapStruct
How to use hidden_field_tag
How to use TreeSet
[How to use label]
How to use identity
How to use hashes
How to use JUnit 5
How to use Dozer.mapper
How to use Gradle
How to use org.immutables
How to use java.util.stream.Collector
How to use VisualVM
How to use Map
[Java] How to use Map
How to use Chain API
[Rails] How to use enum
How to use java Optional
How to use JUnit (beginner)
How to use Ruby return
[Rails] How to use enum
How to use @Builder (Lombok)
[Swift] How to use UserDefaults
How to use java class
How to use Swift UIScrollView
How to use Big Decimal
[Java] How to use Optional ②
[Java] How to use removeAll ()
How to use String [] args
[Java] How to use string.format
How to use rails join
How to use Java Map
Ruby: How to use cookies
How to use dependent :: destroy
How to use Eclipse Debug_Shell
How to use Apache POI
[Rails] How to use validation
How to use Java variables
[Rails] How to use authenticate_user!
[Rails] How to use "kaminari"
How to use GC Viewer
[Java] How to use Optional ①
How to use Lombok now
[Creating] How to use JUnit
[Rails] How to use Scope
How to use the link_to method
[Rails] How to use gem "devise"
How to use Lombok in Spring
How to use StringBurrer and Arrays.toString.
How to use Java HttpClient (Get)
How to use scope (JSP & Servlet)