#A7701. 最后一块石头

最后一块石头

Description

有一堆石头,每块石头的重量都是正整数。

每一回合,从中选出两块 最重的 石头,然后将它们一起粉碎。假设石头的重量分别为 x 和 y,且 x <= y。那么粉碎的可能结果如下:

如果 x == y,那么两块石头都会被完全粉碎;

如果 x != y,那么重量为 x 的石头将会完全粉碎,而重量为 y 的石头新重量为 y-x。

最后,最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下,就返回 0。

Input Format

第一行输入n,表示有n块石头。

第二行输入n个数,每个数用空格隔开,表示每块石头的重量。

Output Format

输出一个整数,如果剩1块石头输出重量,没有石头输出0。

6
2 7 4 1 8 1
1

Source

信奥星OJ http://127.0.0.1