6 一维数组综合应用

正在加载视频播放器…

GESP C++ 三级：一维数组综合应用

核心目标：在掌握一维数组基本操作的基础上，综合运用数组与模拟法、枚举法、统计法，解决多逻辑组合的编程问题，熟悉GESP三级真题的命题趋势与解题套路。
数组是“数据容器”，模拟法是“忠实复现规则”，枚举法是“逐一验证可能”；综合题的难点不在语法，而在读懂规则、理清步骤、守住边界。

一、题型一：数组 + 模拟法

1. 核心方法论

模拟法的本质是：把题目描述的规则，用代码一步一步忠实复现出来。不需要数学推导，不需要找公式，只需要“照猫画虎”。

模拟法解题三步框架：

第一步：识别状态变量（哪些量在变化）
第二步：确定每一步的操作规则（按顺序执行什么）
第三步：确定终止条件（什么时候停止）

2. 真题精讲：数组清零

题目描述：

小A有一个由n个非负整数构成的数组。重复进行以下操作，直到数组只包含0：

找到最大的整数，记其下标为k。如果有多个最大值，选择下标最大的。
从所有不为零的整数中找到最小的整数。
将第一步找到的数减去第二步找到的数。

求需要多少次操作才能使得数组全部变成0。

示例：[2, 3, 4] 需要 7 次操作变成 [0, 0, 0]。

解题思路：

这道题是典型的模拟法——规则非常明确，只需要把三个步骤翻译成代码，循环执行直到数组全为0。

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[105];
    for (int i = 0; i < n; i++) cin >> a[i];

    int ops = 0;
    while (true) {
        // 检查是否全部为0
        bool allZero = true;
        for (int i = 0; i < n; i++) {
            if (a[i] != 0) { allZero = false; break; }
        }
        if (allZero) break;

        // 步骤1：找最大元素，多个取下标最大的
        int maxIdx = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0) {
                if (maxIdx == -1 || a[i] >= a[maxIdx]) {
                    maxIdx = i;   // 注意用 >= 取下标最大的
                }
            }
        }

        // 步骤2：找最小非零元素
        int minVal = 1000000000;
        for (int i = 0; i < n; i++) {
            if (a[i] > 0 && a[i] < minVal) {
                minVal = a[i];
            }
        }

        // 步骤3：最大值减去最小值
        a[maxIdx] -= minVal;
        ops++;
    }

    cout << ops << endl;
    return 0;
}

关键细节：

细节	说明
`a[i] >= a[maxIdx]`	用 `>=` 而非 `>`，保证多个最大值时取下标最大的
`a[i] > 0` 条件	只在非零元素中找最大/最小
`allZero` 检查	每次循环开始前检查，全0则退出
数据规模	n≤100，aᵢ≤100，模拟次数有限，不会超时

3. 模拟法的通用模板

// 1. 读入初始状态
// 2. while (未达到终止条件) {
//        a. 检查终止条件
//        b. 按题目规则，逐步更新状态
//        c. 记录操作次数/输出中间结果
//    }
// 3. 输出最终结果

边界自测规则：每写完一道模拟题，必须自行设计3组边界数据：

n = 1（只有一个元素）
全0数组（一开始就满足终止条件）
全最大值（模拟次数最多的情况）

二、题型二：数组 + 枚举/统计法

1. 核心方法论

枚举法的本质是：遍历所有可能的情况，用条件筛选出正确答案。数组在这里充当“数据容器”和“结果记录器”。

枚举法解题框架：

外层循环：遍历所有可能的“候选”
内层逻辑：对每个候选，判断是否满足条件
结果处理：计数、累加、更新最值、标记

2. 真题精讲：小杨的智慧购物

题目描述：

小杨需要购买M种文具。商店里共有N件文具，每件有种类K和价格P。对于每种文具，只购买最便宜的那一件。计算买齐所有M种文具的最小总花费。

解题思路：

核心是维护一个“每种文具最低价格”的数组，遍历所有商品时不断更新，最后求和。

#include<bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

int main() {
    int m, n;
    cin >> m >> n;

    int minPrice[1005];
    for (int i = 1; i <= m; i++) minPrice[i] = INF;

    for (int i = 0; i < n; i++) {
        int k, p;
        cin >> k >> p;
        if (p < minPrice[k]) {
            minPrice[k] = p;
        }
    }

    int total = 0;
    for (int i = 1; i <= m; i++) {
        total += minPrice[i];
    }
    cout << total << endl;
    return 0;
}

关键细节：

细节	说明
数组大小	`1005`，留足余量，防止种类编号越界
初始值设为INF	保证第一次遇到真实价格时一定能更新
下标从1开始	种类编号是1~M，数组下标与之对应
时间复杂度	O(N)，只需遍历一遍商品

3. 统计法：桶数组的应用

当元素范围有限且连续时，可以用数组作“桶”统计频次。

直方图统计（GESP三级常考）：

// 统计数组中每个数出现的次数，只统计到最大值m
const int M = 1005;
int bucket[M] = {0};
int maxVal = 0;

for (int i = 0; i < n; i++) {
    bucket[arr[i]]++;
    if (arr[i] > maxVal) maxVal = arr[i];
}

for (int v = 0; v <= maxVal; v++) {
    cout << bucket[v] << endl;   // 每个数出现的次数
}

桶数组的适用条件：

元素范围已知且有限（如0~1000）。
需要频繁查询某个值出现的次数。
不需要对元素本身做复杂运算。

三、题型三：数组 + 多条件组合

1. 核心方法论

三级综合题的最新趋势是“多条件组合”——不再是单一操作，而是要求在一个循环中完成多个统计目标，或者在多个条件之间做判断和筛选。

多条件组合题的解题框架：

1. 列出所有需要统计/判断的条件
2. 确定哪些条件可以在同一次遍历中完成
3. 设计状态变量（计数器、最值变量、标记数组）
4. 一次遍历中同步更新所有状态
5. 输出所有统计结果

2. 典型模型：一次遍历完成多项统计

题目：输入n个数，统计其中正数个数、负数个数、零的个数，并求所有数的绝对值之和。

int positive = 0, negative = 0, zero = 0;
long long absSum = 0;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (x > 0) positive++;
    else if (x < 0) negative++;
    else zero++;

    if (x >= 0) absSum += x;
    else absSum += -x;
}

cout << positive << " " << negative << " " << zero << " " << absSum << endl;

关键：所有统计变量必须在循环外初始化，循环内只更新。

3. 典型模型：多条件筛选

题目：从数组中找出同时满足以下条件的元素：大于平均值、是偶数、能被3整除。输出这些元素。

// 第一步：求平均值
int sum = 0;
for (int i = 0; i < n; i++) sum += arr[i];
double avg = 1.0 * sum / n;

// 第二步：多条件筛选
for (int i = 0; i < n; i++) {
    if (arr[i] > avg && arr[i] % 2 == 0 && arr[i] % 3 == 0) {
        cout << arr[i] << " ";
    }
}

4. 典型模型：标记数组的应用

标记数组用于记录“某个位置/某个值是否被访问过”或“是否满足条件”。

题目：找出数组中所有重复出现的元素（只输出一次）。

const int M = 1005;
bool appeared[M] = {false};   // 标记是否已经出现过
bool printed[M] = {false};    // 标记是否已经输出过

for (int i = 0; i < n; i++) {
    if (appeared[arr[i]] && !printed[arr[i]]) {
        cout << arr[i] << " ";
        printed[arr[i]] = true;
    }
    appeared[arr[i]] = true;
}

四、易错点与边界处理

1. 综合应用题的高频失分点

失分点	原因	正确做法
下标写反	`arr[i]` 写成 `arr[j]`	遍历时先在草稿纸上画出前3个元素的下标
循环边界错误	`i < n` 写成 `i <= n`	三级数组题统一用 `i < n`，除非题目明确要求1~n
累加变量在循环内初始化	`int sum = 0;` 写在循环体内	所有统计变量必须在循环外初始化
最值初值取0	数组全为负数时结果错误	最值初值取 `arr[0]` 或一个足够大/小的数
忘记特判n=0	空数组时循环不执行，但逻辑可能出错	读入后先检查 `if (n == 0)`
数组大小不够	`n` 可能达到1000，数组只开了100	数组大小留足余量，通常开 `n + 5`
模拟题漏步骤	题目描述三步，代码只写了两步	把题目步骤逐条列在注释里，逐条对照

2. 三级编程题的“3组边界自测”规则

每写完一道数组综合题，必须自行设计3组边界测试数据：

第1组：n = 1（最小规模，验证基本逻辑）
第2组：全0 / 全相同值（特殊输入，验证终止条件）
第3组：全最大值（验证是否会溢出、是否会超时）

3. 数组遍历的“画图对照法”

数组遍历类题目，写完后先在草稿纸上画出前3个元素的运行结果，和代码输出对照，避免下标写反。这类错误在近3场考试里占编程题丢分的40%以上。

五、速查表

需求	核心写法	关键细节
模拟法	`while (未终止) { 按规则更新; ops++; }`	步骤不能少、顺序不能乱
枚举法	`for (所有可能) { if (条件) 处理; }`	条件要覆盖全部情况
统计法	`bucket[值]++;`	桶大小要足够
最值更新	`if (x < minv) minv = x;`	初值取INF或arr[0]
多条件统计	循环外初始化，循环内更新	所有计数器同步维护
标记数组	`bool visited[M] = {false};`	只标记，不修改原数组
边界自测	n=1、全0、全最大值	每组都要手动验证

六、总结

一维数组综合应用是从“语法”迈向“算法”的关键台阶。

三级数组长度必须是编译期常量，不能用变长数组。
模拟法的核心是“忠实复现规则”，步骤不能少、顺序不能乱。
枚举法的核心是“遍历所有可能，用条件筛选”。
统计法的核心是“桶数组计数，一次遍历完成”。
多条件组合题，所有状态变量必须在循环外初始化。
最值初值取 arr[0] 或足够大/小的数，不要取0。
数组遍历统一用 i < n，边界条件是最大的坑。
每道题写完必须做“3组边界自测”：n=1、全0、全最大值。
数组遍历题写完后画前3个元素的运行结果，避免下标写反。
近3场考试难度上浮，细节处理比“能不能做出来”更重要。

复习建议：先把“数组清零”和“智慧购物”两道真题彻底吃透，理解模拟法和统计法的解题框架；再练“多条件统计”类题目，培养一次遍历完成多项任务的能力。每道题做完后，用n=1、全0、全最大值三组数据手动验证，确保边界处理无误。考试中先读懂题目规则，列出所有需要统计的量，再设计循环结构，最后逐行检查边界和输出格式。