優先度付きQueueの使い方

#ABC141のD問題を地獄のようなコードで解いてしまった
昨晩のAtCoder Beginner Contest 141を地獄のようなコードで回答してしまった。
問題

優先度付きQueue(PriorityQueue)を知らぬが故、sort->pop->push->sort...を繰り返すという
脳筋技を使ってしまったので、その反省

##経緯
###問題文読みたくない人向けのさっくりした説明

• すべての商品を買うための値段を求めたい
• それぞれの商品には値段がついている
• ただし、N枚のクーポンを持っていて、クーポンを一つ使うと一つの商品の値段が半額になる

といった問題
※若干意訳あり

###筆者の脳内基本設計
値段の高いものからクーポン使い切るまで使っていけば安くなるのでは？

凡例:
クーポンが3枚あるとする。
3つの商品があり、値段はそれぞれ下記の通り。
100円,75円,40円

解法:

1. 100円の商品にクーポンを利用(100円->50円)
2. 75円の商品にクーポンを利用(75円->37円)
3. 50円の商品にクーポンを利用(50円->25円)
4. 25円,37円,40円の合計金額は102円なので、これを出力

###ここから地獄
基本設計レベルあたりまでは間違ってなかったと思うのですが、
コードに起こしたときに優先度付きQueueを知らずに、
LinkedList+Collections.sortに頑張ってもらうという記述

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

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

	System.out.println(result);
}

コードの解き方としてはおそらく正常に動作しておりましたが、
もちろんTLEとなり、死亡しました。

###なにが終わっているのか
言わずもがな、最大値を取るために、毎回sortを行っている部分がだめですね…
javaのCollectionのsortは修正マージソートを利用しているため、
商品の数をN,クーポンをMとすると、処理コストはN log(N)×M回処理が行われていることになる。

##こういったときに使えるPriorityQueueクラス
優先度付きキューのクラス(PriorityQueue)を使うことによって解消

###How to use PriorityQueue
使い方は至って簡単。
priorityQueueクラスを宣言し、addクラスで設定、
peakメソッドで参照(get的な動作),pollメソッドで取出し(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}
	}

上記の例だと、最小値の1が取り出される。
(Queue内は2,3,4が残っている)

降順にしたいのであれば、コンストラクタの引数に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}
	}

##優先度付きQueueを用いて、再度提出

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

結果はAC,179msとだいぶ早く処理してくれました。