868. Smashing the Two Heaviest
You have n stones with given weights. While two or more remain, take the
two HEAVIEST and smash them together:
equal weights both are destroyed
different weights both are destroyed and a stone of the difference appears
Print the weight of the last remaining stone, or 0 if none remain.
A max-heap is the structure: the two heaviest are wanted repeatedly, and the stone produced by a smash goes back in and may be heavier than stones still waiting. Sorting once and walking the list cannot account for that.
Most heap libraries are min-heaps. Negating every weight on the way in and out turns one into a max-heap, which is worth knowing because it avoids writing a second implementation.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ weight ≤ 100000`
Input
The first line contains an integer n.
The second line contains n space-separated stone weights.
Output
Print one integer: the weight of the last stone, or 0 if no stone remains.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.