[JAVA] Comment utiliser Queue avec priorité

J'ai résolu le problème D de ABC141 avec un code infernal

J'ai répondu au concours AtCoder Beginner Contest 141 hier soir avec un code infernal. Problème

Parce que je ne connais pas la file d'attente prioritaire (file d'attente prioritaire), il répète tri-> pop-> push-> tri ... J'ai utilisé la technique du muscle cérébral, donc je le regrette

Contexte

Une explication rapide pour ceux qui ne veulent pas lire l'énoncé du problème

• ** Je veux trouver le prix ** pour acheter tous les produits ** ――Chaque produit a un prix Cependant, si vous avez N coupons et utilisez un coupon, le prix d'un produit sera réduit de moitié **

Des problèmes tels que

• Il y a une traduction

Conception de base dans mon cerveau

N'est-ce pas moins cher si vous utilisez ceux avec le prix le plus élevé jusqu'à ce que les coupons soient épuisés?

** Guide d'utilisation: ** Supposons que vous ayez trois coupons. Il existe trois produits et les prix sont les suivants. 100 yens, 75 yens, 40 yens

Solution:

1. Utilisez des coupons pour des produits de 100 yens (100 yens> 50 yens)
2. Utilisez des coupons pour des produits de 75 yens (75 yens> 37 yens)
3. Utilisez des coupons pour des produits de 50 yens (50 yens> 25 yens)
4. Le montant total de 25 yens, 37 yens et 40 yens est de ** 102 yens **.

L'enfer d'ici

Je ne pense pas que c'était mal jusqu'au niveau de conception de base Sans connaître la file d'attente prioritaire lors du réveil dans le code Description que LinkedList + Collections.sort fera de son mieux

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

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

	System.out.println(result);
}

Cela a probablement bien fonctionné pour résoudre le code, Bien sûr, il est devenu TLE et est mort.

Ce qui est fini

Inutile de dire que la partie qui trie à chaque fois pour obtenir la valeur maximale est inutile ... Puisque la sorte de collection java utilise un tri de fusion modifié, En supposant que le nombre de produits est N et que le coupon est M, le coût de traitement est N log (N) × M fois.

Classe PriorityQueue qui peut être utilisée dans de tels cas

Résolu à l'aide d'une classe Priority Queue (PriorityQueue)

How to use PriorityQueue C'est très simple à utiliser. Déclarez la classe priorityQueue et définissez-la avec la classe add, Référence avec la méthode de pointe (comportement de type get), extraction avec la méthode de sondage (comportement de type pop)

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

Dans l'exemple ci-dessus, la valeur minimale de 1 est récupérée. (2,3,4 restent dans la file d'attente)

Si vous voulez dans l'ordre décroissant, définissez Collections.reverseOrder () dans l'argument du constructeur

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

Soumettez à nouveau à l'aide de la file d'attente prioritaire

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

Le résultat était ** AC ** </ font>, 179ms, qui a été traité très rapidement.