← 返回 oracle 的题目列表Leetcode Heap Original Question
类型：online_judge
Given a collection of stones, each stone has a positive integer weight.
Every round, choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of smashing them is:
If x == y, both stones are destroyed.
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
Return the weight of the last remaining stone. If there are no stones left, return 0.
Input format:
The first line contains an integer n, the number of stones.
The second line contains n integers, representing the weights of the stones.
Output format:
Output a single integer, the weight of the last remaining stone.
Example:
Input
6
2 7 4 1 8 1
Output
1
Constraints:
1 <= n <= 1000
Each stone's weight is 1 to 1000.
Example
Input
6
2 7 4 1 8 1