B4413 [GESP202509 三级] 数组清零

题目描述

小 A 有一个由 $n$ 个非负整数构成的数组 $a=[a_1,a_2,\dots ,a_n]$。他会对阵组 $a$ 重复进行以下操作，直到数组 $a$ 只包含 0。在一次操作中，小 A 会依次完成以下三个步骤：

1. 在数组 $a$ 中找到最大的整数，记其下标为 $k$。如果有多个最大值，那么选择其中下标最大的。
2. 从数组 $a$ 所有不为零的整数中找到最小的整数 $a_j$。
3. 将第一步找出的 $a_k$ 减去 $a_j$。

例如，数组 $a=[2,3,4]$ 需要 7 次操作变成 $[0,0,0]$：

$$[2,3,4]\to [2,3,2]\to [2,1,2]\to [2,1,1]\to [1,1,1]\to [1,1,0]\to [1,0,0]\to [0,0,0]$$

小 A 想知道，对于给定的数组 $a$，需要多少次操作才能使得 $a$ 中的整数全部变成 0。可以证明，$a$ 中整数必然可以在有限次操作后全部变成 0。你能帮他计算出答案吗？

输入格式

第一行，一个正整数 $n$，表示数组 $a$ 的长度。

第二行，$n$ 个非负整数 $a_1,a_2,\dots ,a_n$，表示数组 $a$ 中的整数。

输出格式

一行，一个正整数，表示 $a$ 中整数全部变成 0 所需要的操作次数。

输入输出样例 #1

输入 #1

3
2 3 4

输出 #1

7

输入输出样例 #2

输入 #2

5
1 3 2 2 5

输出 #2

13

说明/提示

对于所有测试点，保证 $1\le n\le 100$，$0\le a_i\le 100$。

解析

模拟，详见代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[1005];
int ans=0;
int main (){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(1){
        int mx=1;//第几个数最大,默认值为第一个
        for(int i=1;i<=n;i++){//循环找到最大值的位置
            if (a[i]>a[mx]){
                mx=i;
            }
        }
        int mn=mx;//第几个数最小，默认值为最大那个
        for(int i=1;i<=n;i++){//循环找到最小值的位置
            if (a[i]>0&&a[i]<a[mn]){
                mn=i;
            }
        }
        //如果最大值为0，则操作结束
        if (a[mx]==0) break;
        a[mx]-=a[mn];//模拟最大值减去最小值
        ans++;//增加操作次数
    }
    cout<<ans;
    return 0;
}