G3019 [GESP202509 三级] 数组清零 题解

知识点：数组模拟、最值、条件选择。

解题思路

反复找出最小正数lo及最靠后的最大值位置hi，将a[hi]减lo并计数，直到全部变成0。

为什么正确

每轮严格按照选取规则执行一次操作，非负数组和严格下降，终止时计数即为操作次数。

易错点

最大值并列时选择最右位置；最小值只从正数中选，不能包含0。

复杂度

设操作数K，时间O(Kn)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,ans=0;
    cin>>n;
    vector<int>a(n);
    for(int &x:a)cin>>x;
    while(true) {
        int hi=-1,lo=101;
        for(int i=0;i<n;i++) {
            if(a[i]>0)lo=min(lo,a[i]);
            if(hi==-1||a[i]>=a[hi])hi=i;
        }
        if(a[hi]==0)break;
        a[hi]-=lo;
        ans++;
    }
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。