【GESP】C++三级真题 luogu-B3867 [GESP202309 三级] 小杨的储蓄
GESP三级真题,一维数组相关,难度★✮☆☆☆。
luogu-B3867 [GESP202309 三级] 小杨的储蓄
题目要求
题目描述
小杨共有 $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
输入 #1
1
2
2 3
0 1 0
输出 #1
1
4 2
输入输出样例 #2
输入 #2
1
2
3 5
0 0 0 2 0
输出 #2
1
11 0 4
说明/提示
样例解释 1:
小杨在第 $1$ 天、第 $2$ 天、第 $3$ 天分别向 $0$ 号、 $1$ 号、 $0$ 号存钱罐存了 $1$ 元钱、 $2$ 元钱、 $3$ 元钱,因此 $0$ 号存钱罐有 $1+3=4$ 元钱,而 $1$ 号存钱罐有 $2$ 元钱。
题目分析
解题思路
本题的解题思路可以分为以下几个步骤:
- 读取输入数据:
- 读取存钱罐数量N和天数D
- 创建长度为N的数组,用于记录每个存钱罐的金额,初始化为0
- 处理每天的存钱操作:
- 循环D天,每天:
- 读取当天选择的存钱罐编号
- 将当天对应的金额(即天数)加到对应存钱罐中
- 循环D天,每天:
- 输出结果:
- 遍历数组,输出每个存钱罐的最终金额
举例说明: 假设N=2,D=3,存钱顺序为[0,1,0]
- 第1天:向0号存钱罐存1元
- 第2天:向1号存钱罐存2元
- 第3天:向0号存钱罐存3元 最终0号存钱罐有4元(1+3),1号存钱罐有2元
复杂度分析:
- 时间复杂度:$O(D)$,需要处理D天的存钱操作
- 空间复杂度:$O(N)$,需要一个长度为N的数组存储结果
示例代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
int main() {
// 声明变量N和D,分别表示存钱罐数量和天数
int N, D;
std::cin >> N >> D;
// 创建数组存储每个存钱罐的金额,初始化为0
int ary[N] = {0};
// 循环D天,每天读取存钱罐编号并累加对应金额
for (int i = 1; i <= D; i++) {
int idx;
std::cin >> idx;
ary[idx] += i; // 第i天存入i元钱
}
// 输出每个存钱罐的最终金额
for (int i = 0; i< N; i++) {
std::cout << ary[i] << " ";
}
return 0;
}
所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲要点、知识拓展和练习题目清单详见C++学习项目主页
“luogu-”系列题目已加入洛谷Java、C++初学团队,作业清单,可在线评测,团队名额有限,欢迎加入。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
本文由作者按照 CC BY 4.0 进行授权