文章

【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$ 元钱。


题目分析

解题思路

本题的解题思路可以分为以下几个步骤:

  1. 读取输入数据:
    • 读取存钱罐数量N和天数D
    • 创建长度为N的数组,用于记录每个存钱罐的金额,初始化为0
  2. 处理每天的存钱操作:
    • 循环D天,每天:
      • 读取当天选择的存钱罐编号
      • 将当天对应的金额(即天数)加到对应存钱罐中
  3. 输出结果:
    • 遍历数组,输出每个存钱罐的最终金额

举例说明: 假设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 进行授权