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

2 3
0 1 0

输出 #1

4 2

输入输出样例 #2

输入 #2

3 5
0 0 0 2 0

输出 #2

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的数组存储结果

{% include custom/custom-post-content-inner.html %}

示例代码

#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;
}

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号