一维数组的基本应用

C++一维数组基本应用（不包括变长数组）：遍历、统计、查找、计数等常见应用。

定义好数组之后，三级要会用循环走遍每一个下标做事情。遍历是 for (int i = 0; i < n; ++i) 访问 a[i]。在此之上：求和或求平均属于统计；扫一遍记下最大 / 最小及其下标；按值查找第一次出现的位置；按条件计数（大于某数、等于某数的个数）。这些都不需要新语法，关键是循环边界与「当前最优 / 计数器」的更新时机。仍不包括变长数组，n 用固定容量承接。

客观题会给一小段遍历代码，问循环结束后的和、最大值或计数。编程题几乎每场都有「读入 n 个数再处理」：清零、替换、找满足条件的元素个数。认证标准规定考试时长为 120 分钟，两道编程各 25 分，先写对一遍扫描，再考虑是否需要第二遍。

int a[8] = {3, 7, 2, 7, 9, 1, 4, 7};
int n = 8, cnt = 0, mx = a[0];
for (int i = 0; i < n; ++i) {
    if (a[i] == 7) ++cnt;
    if (a[i] > mx) mx = a[i];
}
// cnt == 3，mx == 9

查找「第一个」时找到即可 break；统计「有多少个」则必须走完。初始化最大值时不要默认成 0——数组可能全是负数。

在下列代码的横线处填写（），可以使得输出是 “2”。

#include <iostream>
using namespace std;
int main() {
    int array[5] = {3, 7, 5, 2, 4};
    int min = 0;
    for (int i = 0; i < 5; i++)
        if (________) // 在此处填写代码
            min = array[i];
    cout << min << endl;
    return 0;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写版式题干 · 第 7 行
原卷作 if (________) ，常规写法应为 if (______)
洛谷有题把填空横线写成 6 个下划线；官方 PDF 第 5 页为 8 个下划线。已按页面图像恢复。
已按官方原件恢复：现为原卷原文

min > array[i]

min < array[i]

min = array[i]

以上均不对。

编程题

春游

C++时间 1 s内存 128 MB标准输入输出

老师带领同学们春游。已知班上有 $N$ 位同学，每位同学有从 $0$ 到 $N-1$ 的唯一编号。到了集合时间，老师确认是否所有同学都到达了集合地点，就让同学们报出自己的编号。到达的同学都会报出自己的编号，不会报出别人的编号，但有的同学很顽皮，会多次报出。你能帮老师找出有哪些同学没有到达吗 ?。

输入格式

输入包含 $2$ 行。第一行包含两个整数 $N$ 和 $M$ ，表示班级有 $N$ 位同学，同学们共有 $M$ 次报出编号。约定 $2 \le N,M \le 1000$ 。
第二行包含 $M$ 个整数，分别为 $M$ 次报出的编号。约定所有编号是小于 $N$ 的非负整数。

输出格式

输出一行。如果所有同学都到达，则输出 $N$ ；否则由小到大输出所有未到达的同学编号，空格分隔。

样例

输入 1

3 3
0 2 1

输出 1

输入 2

3 5
0 0 0 0 0

输出 2

1 2

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

在下列代码的横线处填写（），可以使得输出是“120”。

填空程序：对数组元素做累计运算

#include <iostream>
using namespace std;

int main() {
    int array[5] = {1, 2, 3, 4, 5};
    int res = 0;
    for (int i = 0; i < 5; i++)
        ______; // 在此处填入代码
    cout << res << endl;
    return 0;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写版式题干
原卷作 ![填空程序：对数组元素做累计运算|480](content/assets/gesp-cpp-l3-2023-09/fig-03.png)
官方 PDF 第 4 页该程序是嵌入位图；已抽为 fig-03.png（宽 480），并保留洛谷转写的代码围栏供阅读。
已按官方原件恢复：现为原卷原文

res += array[i];

res *= array[i]

res = array[i]

以上均不对。

编程题

小杨的储蓄

C++时间 1 s内存 128 MB标准输入输出

小杨共有 $N$ 个储蓄罐，编号从 $0$ 到 $N-1$ 。从第 $1$ 天开始，小杨每天都会往存钱罐里存钱。具体来说，第 $i$ 天他会挑选一个存钱罐 $a_i$ ，并存入 $i$ 元钱。过了 $D$ 天后，他已经忘记每个储蓄罐里都存了多少钱了，你能帮帮他吗？

输入格式

输入 $2$ 行，第一行两个整数 $N,D$ ；第二行 $D$ 个整数，其中第 $i$ 个整数为 ${a_i}$ （保证 $0 \le a_i \le N-1$ ）。

每行的各个整数之间用单个空格分隔。

保证 $1 \le N \le 1,000$ ； $1 \le D \le 1,000$ 。

输出格式

输出 $N$ 个用单个空格隔开的整数，其中第 $i$ 个整数表示编号为 $i-1$ 的存钱罐中有多少钱（ $i=1, \cdots ,N$ ）。

样例

输入 1

2 3
0 1 0

输出 1

4 2

样例解释 1：

小杨在第 $1$ 天、第 $2$ 天、第 $3$ 天分别向 $0$ 号、 $1$ 号、 $0$ 号存钱罐存了 $1$ 元钱、 $2$ 元钱、 $3$ 元钱，因此 $0$ 号存钱罐有 $1+3=4$ 元钱，而 $1$ 号存钱罐有 $2$ 元钱。

输入 2

3 5
0 0 0 2 0

输出 2

11 0 4

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

执行 C++ 代码，将输出 $1$ $3$ $5$ $7$ $9$ ， $9$ 之后还有一个空格。()

int list[10]={1,2,3,4,5,6,7,8,9,10};
for(int i=0;i<10;i+=2)
{
    cout<<list[i]<<" ";
}

√（正确）

×（错误）

下面 C++ 代码执行后数组中大于 $0$ 的数的特征是（）。

int main()
{
    int a[20],i;
    for(i = 0; i < 20; i++)
        a[i] = i+1;

    for(int i = 0; i < 20; i++)
        if((a[i]%2)&&(a[i]%3))
            a[i] = 0;

    for(i = 0; i < 20; i++)
        if(a[i])
            cout << a[i] << " ";


    cout << endl;
    return 0;
}

$2$ 的倍数

$3$ 的倍数

能被 $2$ 或 $3$ 整除的数

能被 $2$ 和 $3$ 同时整除的数

对定义的数组 int a[7] = {2, 0, 2, 4, 3, 1, 6}，可以用简单循环就找到其中最小的整数。（）

√（正确）

×（错误）

在下列代码的横线处填写（），可以使得输出是“7”。

#include <iostream>
using namespace std;

int main() {
    int array[5] = {3，7，5，2，4};

    int max = 0;
    for(int i=0; i<5; i++)
        if(______________)  // 在此处填入代码
            max = array[i];

    cout << max << endl;
    return 0;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写符号不一致题干 · 第 5 行
原卷作 int array[5] = {3，7，5，2，4}; ，常规写法应为 int array[5] = {3, 7, 5, 2, 4};
洛谷把原卷全角逗号改成 ASCII 逗号并加空格；已按 PDF 第 4 页字形列位恢复。并补上洛谷未闭合的代码围栏。
已按官方原件恢复：现为原卷原文

max > array[i]

max < array[i]

max = array[i]

以上均不对

小杨在做数学题，题目要求找出从 $1$ 到 $35$ 中能被 $7$ 整除的数字，即 $[7, 14, 21, 28, 35]$ ，则横线处应填入哪个代码？（）

#include <iostream>
using namespace std;

int main() {
    int arr[35];

    int count = 0;
    for (int i = 1; i <= 35; i++) {
        if (i % 7 == 0)
            __________________________  // 在此处填入代码
    }

    for (int i = 0; i < count; i++)
        cout << arr[i] << endl;

    return 0;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写版式题干
原卷作 __________________________ // 在此处填入代码
洛谷缩短了填空下划线；已按 PDF 第 4–5 页列位恢复。
已按官方原件恢复：现为原卷原文

arr[count++] = i;

arr[i] = count++;

arr[i] = count;

arr[count] = count++;

某小学男子篮球队招募新成员，要求加入球队的成员身高在 $135$ 厘米以上（不含 $135$ 厘米）。本次报名的人员有 $10$ 人，他们的身高分别是 $125$ 、 $127$ 、 $136$ 、 $134$ 、 $137$ 、 $138$ 、 $126$ 、 $135$ 、 $140$ 、 $145$ 。完善以下代码，求出本次球队能够招募到新成员的人数？（）

#include <iostream>
using namespace std;

int main() {
    int arr[10] = {125, 127, 136, 134, 137, 138, 126, 135, 140, 145};

    int count = 0;
    for(int i=0; i<10; i++)
        __________________________  // 在此处填入代码

    cout << count << endl;
    return 0;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写版式题干
原卷作 __________________________ // 在此处填入代码
洛谷缩短了填空下划线；已按 PDF 第 6 页列位恢复。
已按官方原件恢复：现为原卷原文

count = arr[i]>135? 1: 0;

count += arr[i]>135? 1: 0;

count++;

以上都不对

编程题

寻找倍数

C++时间 1 s内存 512 MB标准输入输出

小杨有一个包含 $n$ 个正整数的序列 $A=[a_1,a_2,\dots,a_n]$ ，他想知道是否存在 $i(1\leq i\leq n)$ 使得 $a_i$ 是序列 $A$ 中所有数的倍数。

输入格式

第一行包含一个正整数 $t$ ，代表测试用例组数。

接下来是 $t$ 组测试用例。对于每组测试用例，一共两行。

其中，第一行包含一个正整数 $n$ ；第二行包含 $n$ 个正整数，代表序列 $A$ 。

输出格式

对于每组测试用例，如果存在 $i(1\leq i\leq n)$ ，满足对于所有 $k(1\leq k\leq n)$ $a_i$ 是 $a_k$ 的倍数，输出 Yes，否则输出 No。

样例

输入 1

输出 1

Yes
No

【样例解释】

对于第一组数据，对于 $a_3=4$ ，满足 $a_3$ 是 $a_1$ 和 $a_2$ 的倍数。

数据范围

对于全部数据，保证有 $1\leq t\leq 10$ ， $1\leq n\leq 10^5$ ， $1\leq a_i\leq 10^9$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

编程题

平衡序列

C++时间 1 s内存 512 MB标准输入输出

小杨有一个包含 $n$ 个正整数的序列 $a$ 。他认为一个序列是平衡的当且仅当存在一个正整数 $i$ （ $1 \leq i < n$ ）使得序列第 $1$ 到第 $i$ 个数字的总和等于第 $i + 1$ 到第 $n$ 个数字的总和。

小杨想请你判断序列 $a$ 是否是平衡的。

输入格式

本题单个测试点内包含多组测试数据。第一行是一个正整数 $t$ ，表示测试用例组数。

接下来是 $t$ 组测试用例。对每组测试用例，一共两行。

第一行包含一个正整数 $n$ ，表示序列长度。
第二行包含 $n$ 个正整数，代表序列 $a$ 。

输出格式

对每组测试用例输出一行一个字符串。如果 $a$ 是平衡的，输出 $\texttt{Yes}$ ，否则输出 $\texttt{No}$ 。

样例

输入 1

输出 1

Yes
Yes
No

样例 1 解释

对第一组测试用例，令 $i = 2$ ，有 $1 + 2 = 3$ ，因此序列是平衡的。
对第二组测试用例，令 $i = 2$ ，有 $2 + 3 = 1 + 4$ ，因此序列是平衡的。
对第三组测试用例，不存在满足要求的 $i$ 。

数据规模与约定

对全部的测试数据，保证 $1 \leq t \leq 100$ ， $1 \leq n, a_i \leq 10000$ 。

数据范围

对于全部数据，保证有 $1 \le t \le 100$ ， $1 \le n, a_i \le 10000$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

编程题

数字替换

C++时间 1 s内存 512 MB标准输入输出

小杨有一个包含 $n$ 个数字的序列 $A$ ，即 $A=[a_1,a_2,\ldots,a_n]$ ，他想将其中大于 $k$ 的数字都替换为序列的最大值，将其中小于 $k$ 的数字都替换为序列的最小值，请你帮他计算出替换后的序列。

输入格式

第一行包含两个正整数 $n,k$ ，含义如题面所示。

第二行包含 $n$ 个数字，代表序列 $A$ 。

输出格式

输出 $n$ 个整数，代表替换后的结果。

样例

输入 1

5 0
-2 -1 0 1 2

输出 1

-2 -2 0 2 2

数据范围

对于全部数据，保证有 $1\le n\le 10^5$ ， $|k|,|a_i|\le 10^5$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

以下代码的功能是将数组中的奇数和偶数分别放在数组的前半部分和后半部分，横线处应该填入的是（）

#include <iostream>
using namespace std;

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int left = 0, right = 4;
    while (left < right) {
        while (arr[left] % 2 == 1 && left < right) left++;
        _______________________
        if (left < right) {
            swap(arr[left], arr[right]);
        }
    }
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

while (arr[left] % 2 == 0 && left < right) right--;

while (arr[right] % 2 == 0 && left < right) left--;

while (arr[right] % 2 != 0 && left < right) right--;

while (arr[right] % 2 == 0 && left < right) right--;

编程题

分糖果

C++时间 1 s内存 512 MB标准输入输出

有 $n$ 位小朋友排成一队等待老师分糖果。第 $i$ 位小朋友想要至少 $a_i$ 颗糖果，并且分给他的糖果数量必须比分给前一位小朋友的糖果数量更多，不然他就会不开心。

老师想知道至少需要准备多少颗糖果才能让所有小朋友都开心。你能帮帮老师吗？

输入格式

第一行，一个正整数 $n$ ，表示小朋友的人数。

第二行， $n$ 个正整数 $a_1, a_2, \ldots, a_n$ ，依次表示每位小朋友至少需要的糖果数量。

输出格式

输出一行，一个整数，表示最少需要准备的糖果数量。

样例

输入 1

4
1 4 3 3

输出 1

输入 2

15
314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

输出 2

4508143253

数据范围

对于所有测试点，保证 $1 \leq n \leq 1000$ ， $1 \leq a_i \leq 10^9$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

以下 C++ 代码试图查找数组中的最大值，划线处应填入（）。

#include <iostream>
using namespace std;
int findMax(int arr[], int size) {
    int maxVal = ________; // 划线处
    for (int i = 1; i < size; i++) {
        if (arr[i] > maxVal) {
            maxVal = arr[i];
        }
    }
    return maxVal;
}

原文保真说明：来源改写 1 处（照原卷保留，未作修改）

来源题面被改写版式题干 · 第 4 行
原卷作 int maxVal = ________; // 划线处
洛谷有题划线为 7 个下划线，且 using namespace std; 后多一空行；官方 PDF 第 3 页列位重建为 8 个下划线、无空行，已恢复。
已按官方原件恢复：现为原卷原文

arr[-1]

arr[0]

size

以下代码执行后，数组 arr 的内容是（）

int arr[6] = {1, 2, 3, 4, 5, 6};
for (int i = 0; i < 6; i += 2) {
    arr[i] = arr[i] + arr[i+1];
    arr[i+1] = arr[i] - arr[i+1];
    arr[i] = arr[i] - arr[i+1];
}

$\{2,1,4,3,6,5\}$

$\{1,2,3,4,5,6\}$

$\{3,1,4,2,5,3\}$

$\{1,3,2,5,4,6\}$

编程题

小杨的智慧购物

C++时间 1 s内存 512 MB标准输入输出

小杨的班级要举办一个环保手工作品展览，老师请小杨去文具店购买 $M$ 种不同的文具（例如：铅笔、橡皮、尺子等）。

商店里共有 $N$ 件文具，每件文具都有一个种类编号（从 $1$ 到 $M$ ）和价格。

小杨的预算有限，他想了一个聪明的办法：对于每种文具，他只买最便宜的那一件（如果同种文具有多件价格相同且都是最便宜的，他只会购买其中的一件）。请你帮小杨计算出，买齐这 $M$ 种文具一共需要花费多少钱。

输入格式

第一行两个正整数 $M, N$ ，代表文具的种类数和总数。

之后 $N$ 行，每行两个正整数 $K_i$ 和 $P_i$ ，分别代表第 $i$ 件文具的种类编号和它的价格。数据保证每个种类至少有一件文具可供购买。

输出格式

输出一行，代表购买文具的总价。

样例

输入 1

输出 1

文具清单如下：

文具 1：种类 1，价格 $1$
文具 2：种类 1，价格 $2$
文具 3：种类 1，价格 $1$
文具 4：种类 2，价格 $3$
文具 5：种类 2，价格 $10$

小杨的选择过程：对于种类 1：有三件商品，价格分别为 $1, 2, 1$ 。其中最便宜的价格是 $1$ 。对于种类 2：有两件商品，价格分别为 $3, 10$ 。其中最便宜的价格是 $3$ 。

计算总价：小杨购买这两类文具的总花费为 $1 + 3 = 4$ 。

数据范围

对于所有测试点，保证 $1 \leq M \leq N \leq 10^5$ ， $1 \leq K_i \leq M$ ， $1 \leq P_i \leq 10^3$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB

判题结果

编程题

加密

C++时间 1 s内存 512 MB标准输入输出

小杨同学有一串数字，想把它们变成另一串数字，这个过程叫做加密。

他有一本密码本，密码本告诉你：每个数字应该变成哪个数字。

数字一共有 $10$ 个： $0$ 、 $1$ 、 $2$ 、 $3$ 、 $4$ 、 $5$ 、 $6$ 、 $7$ 、 $8$ 、 $9$ 。

密码本会依次告诉你：

$0$ 要变成什么
$1$ 要变成什么
$2$ 要变成什么
……
$9$ 要变成什么

请你按照密码本，把原来的每个数字都换成新的数字，然后输出。

输入格式

输入共有 $3$ 行。

第一行：一个整数，表示有多少个数字需要加密；

第二行：这些需要加密的数字；

第三行：密码本，一共 $10$ 个数字。

这 $10$ 个数字的意思是：

第 $1$ 个数字：表示 $0$ 加密后变成什么；
第 $2$ 个数字：表示 $1$ 加密后变成什么；
第 $3$ 个数字：表示 $2$ 加密后变成什么；
……
第 $10$ 个数字：表示 $9$ 加密后变成什么。

输出格式

输出加密后的数字。

也就是：把输入第二行里的每个数字，都按照输入第三行的密码本换掉后输出。

样例

输入 1

7
0 2 0 3 4 1 9
9 0 1 2 3 4 5 6 7 8

输出 1

9 1 9 2 3 0 8

第二行要加密的数字是：

0 \ 2 \ 0 \ 3 \ 4 \ 1 \ 9

第三行密码本是：

9 \ 0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ 8

它的意思是：

$0$ 变成 $9$
$1$ 变成 $0$
$2$ 变成 $1$
$3$ 变成 $2$
$4$ 变成 $3$
$5$ 变成 $4$
$6$ 变成 $5$
$7$ 变成 $6$
$8$ 变成 $7$
$9$ 变成 $8$

所以：

$0$ 变成 $9$
$2$ 变成 $1$
$0$ 变成 $9$
$3$ 变成 $2$
$4$ 变成 $3$
$1$ 变成 $0$
$9$ 变成 $8$

最后得到：

9 \ 1 \ 9 \ 2 \ 3 \ 0 \ 8

数据范围

需要加密的数字个数不超过 $20000$ 个，且均为 $0$ 到 $9$ ；密码本中的数字不重复，且均为 $0$ 到 $9$ 。

你的代码（C++）

提交后由评测机编译运行，结果见下方

编辑器加载中…

76 B / 64 KB