OneCoder Avatar
OneCodercoderli.com · 1024 篇博文
三级

C++ 算法考级专栏

🎨 视觉封面

【GESP】C++三级真题 luogu-B4413 [GESP202509 三级] 数组清零

📅 2025-09-30·✍️ OneCoder·计算中...·⏱️ 6 分钟

GESP C++ 2025年9月三级真题,一维数组考点,难度★★☆☆☆。

luogu-B4413 [GESP202509 三级] 数组清零

题目要求

题目描述

小 A 有一个由 个非负整数构成的数组 。他会对阵组 重复进行以下操作,直到数组 只包含 0。在一次操作中,小 A 会依次完成以下三个步骤:

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

例如,数组 需要 7 次操作变成 :

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

输入格式

第一行,一个正整数 ,表示数组 的长度。

第二行, 个非负整数 ,表示数组 中的整数。

输出格式

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

输入输出样例 #1

输入 #1
PLAINTEXT2 行
3
2 3 4
输出 #1
PLAINTEXT1 行
7

输入输出样例 #2

输入 #2
PLAINTEXT2 行
5
1 3 2 2 5
输出 #2
PLAINTEXT1 行
13

说明/提示

对于所有测试点,保证 ,。


题目分析

  1. 模拟过程

按题意循环三步:

  • 找最大非零下标(最右优先);
  • 在非零元素里找最小值;
  • 把最大值减去该最小值,计数+1。
  • 当数组全零时结束。
  1. 复杂度分析
    每轮扫描需要 时间,最坏情况下总操作次数不超过 (每次至少把当前最大值减1,总共需要元素和次),,整体复杂度 ,在题目约束下完全可行。

示例代码

C++43 行
#include <iostream>

int num_ary[105]; // 存放数组,最多100个元素
int main() {
    int n;
    std::cin >> n; // 读入数组长度
    int count = 0; // 记录操作次数
    for (int i = 0; i < n; i++) {
        std::cin >> num_ary[i]; // 读入数组元素
    }
    bool flag = false; // 标记数组是否全为0
    while (true) {
        flag = true; // 假设已全部清零
        int min = 101; // 初始化最小值(大于题设上限100)
        int max = 0;   // 初始化最大值
        int max_idx = -1; // 最大值下标
        for (int i = 0; i < n; i++) {
            if (num_ary[i] != 0) {
                flag = false; // 发现非零,未清零
            } else {
                continue; // 零元素跳过
            }
            // 更新非零最小值
            if (num_ary[i] < min && num_ary[i] != 0) {
                min = num_ary[i];
            }
            // 更新最大值及其下标(取最右)
            if (num_ary[i] >= max) {
                max = num_ary[i];
                max_idx = i;
            }
        }
        if (flag) {
            break; // 全部清零,退出循环
        }
        // 将最大元素减去最小元素
        num_ary[max_idx] -= min;
        count++; // 操作次数+1
    }

    std::cout << count << std::endl; // 输出总操作次数
    return 0;
}

看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!