模拟法

解题思路

方法：直接模拟

由于数据范围较小（$n \leq 100$, $a_i \leq 100$），我们可以直接模拟每次操作的过程。

每次操作的步骤：

1. 遍历数组找到最大值及其下标（选最大的下标）
2. 遍历数组找到最小的非零值
3. 将最大值减去最小非零值
4. 操作次数+1

终止条件：数组中所有元素都为0

---

代码实现

C++ 实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int main(){
   int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int cnt=0;

    while(1){
        int mx_inx=1;//记录最大值的下标
        for(int i=1;i<=n;i++){
            if(a[mx_inx]<a[i])mx_inx=i;
        }

        if(a[mx_inx]==0){//
            break;//跳出循环,因为最大值为0的时候所有值都为0
        }

        int mi_inx=1;//记录最小值的下标
        while(a[mi_inx]==0)mi_inx++;//跳转到第一个不为0的位置.

        for(int i=1;i<=n;i++){
            if(a[i]==0)continue;
            if(a[mi_inx]>a[i])mi_inx=i;//寻找最小值
        }
        a[mx_inx]-=a[mi_inx]; //减法
        cnt++;
    }
    
    cout<<cnt<<endl;
}
}

---

样例验证

样例1：[2, 3, 4]

操作次数	数组状态	最大值(下标)	最小非零值	操作
0	[2, 3, 4]	-	-	初始
1	[2, 3, 2]	4(下标2)	2	4-2=2
2	[2, 1, 2]	3(下标1)	2	3-2=1
3	[2, 1, 1]	2(下标2)	1	2-1=1
4	[1, 1, 1]	2(下标0)	1	2-1=1
5	[1, 1, 0]	1(下标2)	1	1-1=0
6	[1, 0, 0]	1(下标1)	1	1-1=0
7	[0, 0, 0]	1(下标0)	1	1-1=0

答案：7次 ✓