[JAVA] Verwendung der Warteschlange mit Priorität

Ich habe das D-Problem von ABC141 mit einem höllischen Code gelöst

Ich habe gestern Abend den AtCoder Beginner Contest 141 mit höllischem Code beantwortet. Problem

Da ich die Prioritätswarteschlange (Prioritätswarteschlange) nicht kenne, wird sort-> pop-> push-> sort ... wiederholt. Ich habe Gehirnmuskeltechnik angewendet, deshalb bereue ich es

Hintergrund

Eine kurze Erklärung für diejenigen, die die Problemstellung nicht lesen möchten

• ** Ich möchte den Preis finden ** um alle Produkte zu kaufen ** ――Jedes Produkt hat einen Preis ――Wenn Sie jedoch N Gutscheine haben und einen Gutschein verwenden, reduziert sich der Preis für ein Produkt um die Hälfte **

Probleme wie

• Es gibt einige Übersetzungen

Grundlegendes Design in meinem Gehirn

Ist es nicht billiger, wenn Sie diejenigen verwenden, die teuer sind, bis die Gutscheine aufgebraucht sind?

** Gebrauchsanweisung: ** Angenommen, Sie haben drei Gutscheine. Es gibt drei Produkte und die Preise sind wie folgt. 100 Yen, 75 Yen, 40 Yen

Lösung:

1. Verwenden Sie Gutscheine für 100-Yen-Produkte (100-Yen-> 50-Yen).
2. Verwenden Sie Gutscheine für 75-Yen-Produkte (75-Yen-> 37-Yen).
3. Verwenden Sie Gutscheine für 50-Yen-Produkte (50-Yen-> 25-Yen).
4. Der Gesamtbetrag von 25 Yen, 37 Yen und 40 Yen beträgt ** 102 Yen **, also geben Sie diesen aus

Hölle von hier

Ich glaube nicht, dass es bis zur grundlegenden Designebene falsch war. Ohne die priorisierte Warteschlange beim Aufwachen im Code zu kennen Beschreibung, dass LinkedList + Collections.sort sein Bestes geben wird

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++) {
		//Gorilla hier
		Collections.sort(list, Collections.reverseOrder());
		list.add(list.pop() / 2);
	}

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

	System.out.println(result);
}

Es hat wahrscheinlich gut funktioniert, um den Code zu lösen. Natürlich wurde er TLE und starb.

Was ist vorbei?

Unnötig zu erwähnen, dass der Teil, der jedes Mal sortiert wird, um den Maximalwert zu erhalten, nutzlos ist ... Da die Art der Java-Sammlung eine modifizierte Zusammenführungssortierung verwendet, Unter der Annahme, dass die Anzahl der Produkte N und der Coupon M ist, betragen die Verarbeitungskosten N log (N) × M mal.

PriorityQueue-Klasse, die in solchen Fällen verwendet werden kann

Behebung mithilfe einer Priority Queue-Klasse (PriorityQueue)

How to use PriorityQueue Es ist sehr einfach zu bedienen. Deklarieren Sie die priorityQueue-Klasse und legen Sie sie mit der add-Klasse fest. Referenz mit Peak-Methode (get-like Verhalten), Abruf mit Poll-Methode (pop-like Verhalten)

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}
	}

Im obigen Beispiel wird der Mindestwert von 1 abgerufen. (2,3,4 bleiben in der Warteschlange)

Wenn Sie in absteigender Reihenfolge möchten, setzen Sie im Argument des Konstruktors "Collections.reverseOrder ()"

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}
	}

Senden Sie erneut mit der Prioritätswarteschlange

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

Das Ergebnis war ** AC ** </ font>, 179 ms, das sehr schnell verarbeitet wurde.