Last Stone Weight [LeetCode 1046]

https://leetcode.com/contest/weekly-contest-137/problems/last-stone-weight/

N個の石があり、それぞれの重さがわかっている。
最も重い2つの石をぶつけるという操作をできなくなるまで行う。
ぶつけると、

• 同じ重さであれば、2つとも消滅
• 差があれば、差分の石が残る

という結果になる。
最終的に残る石の重さは？
（残らなければ0を答える）

1≦N≦30
1≦重さ≦1000

解説

https://leetcode.com/contest/weekly-contest-137/submissions/detail/229840104/

シミュレーションしていこう。
最も重い石を取り出すという作業はpriority queueを使うと簡単にできる。
全部priority queueに突っ込んで、2個ずつ取り出しながら操作を行っていこう。

class Solution {
public:
	int lastStoneWeight(vector<int>& stones) {
		priority_queue<int> q;
		fore(i, stones) q.push(i);

		while (2 <= q.size()) {
			int x = q.top(); q.pop();
			int y = q.top(); q.pop();

			int d = abs(x - y);
			if (0 < d) q.push(d);
		}

		if (q.size() == 0) return 0;
		int ans = q.top();
		return ans;
	}
};