第 1 题 数组清零
题面描述
小 A 有一个由 $n$ 个非负整数构成的数组 $a=[a_1,a_2,\cdots,a_n]$。他会对数组$a$ 重复进行以下操作,直到数组 $n$ 只包含$0$。在一次操作中,小 A 会依次完成以下三个步骤:
1. 在数组 $a$ 中找到最大的整数,记其下标为 $K$。如果有多个最大值,那么选择其中下标最大的。
2. 从数组 $a$ 所有不为零的整数中找到最小的整数 。
3. 将第一步找出的 $a_k$ 减去 $a_j$。
例如,数组 $a=[2,3,4]$ 需要 $7$ 次操作变成 $[0,0,0]$:
$[2,3,4] \rightarrow [2,3,2] \rightarrow [2,1,2] \rightarrow [2,1,1] \rightarrow [1,1,1] \rightarrow [1,1,0] \rightarrow [1,0,0] \rightarrow [0,0,0]$
小 A 想知道,对于给定的数组 $a$,需要多少次操作才能使得 $a$中的整数全部变成 $0$。可以证明,$a$ 中整数必然可以在
有限次操作后全部变成 $0$。你能帮他计算出答案吗?
输入格式
第一行,一个正整数 $n$,表示数组 $a$ 的长度。
第二行,$n$ 个非负整数 $a_1,a_2,\cdots,a_n$,表示数组 $a$ 中的整数。
输出格式
一行,一个正整数,表示 $a$ 中整数全部变成 $0$ 所需要的操作次数。
数据要求
对于所有测试点,保证 $1 \le n \le 100$,$0 \le a_i \le 100$ 。