小杨的储蓄

题目分析

小杨有 $N$ 个编号为 $0 \sim N-1$ 的储蓄罐。在接下来的 $D$ 天里，他每天会选择一个储蓄罐存钱，第 $i$ 天（$i$ 从 $1$ 开始）会存入 $i$ 元。现在过了 $D$ 天，小杨忘记了每个罐子里有多少钱，需要你帮忙计算出每个储蓄罐的最终余额。

输入：
第一行两个整数 $N$ 和 $D$；第二行 $D$ 个整数 $a_i$，依次表示第 $1$ 天到第 $D$ 天选择的储蓄罐编号。
输出：
一行 $N$ 个整数，表示编号 $0 \sim N-1$ 的储蓄罐中的总金额，用空格隔开。

解题思路

题目思路非常直观：我们需要维护一个大小为 $N$ 的数组，记录每个储蓄罐当前的存款总额。

1. 初始化一个长度为 $N$ 的数组 jar，所有元素置为 $0$。
2. 遍历每一天 $i$（$i$ 从 $1$ 循环到 $D$）：
   • 读入当天选择的储蓄罐编号 $a$。
   • 将 $i$ 元加入到对应储蓄罐：jar[a] += i。
3. 最后将 jar 数组按编号顺序输出。

因为第 $i$ 天存入的金额恰好是 $i$，所以直接在循环变量中就能获得当天的存款金额，无需额外计算。

算法说明

用自然语言描述算法步骤：

• 输入阶段：读入 $N$ 和 $D$，创建一个长度为 $N$ 的整数数组并初始化为全 $0$。
• 处理阶段：执行 $D$ 次循环，循环变量 $i$ 从 $1$ 到 $D$。每次读入一个整数 $a$，执行 jar[a] += i。
• 输出阶段：为了满足输出格式（末尾不含多余空格），先输出 jar[0]，再依次输出 " jar[1]" ... " jar[N-1]"，最后换行。

该算法保证了每个储蓄罐的总金额等于所有存入该罐的天数编号之和。

时间复杂度分析

• 初始化数组：$O(N)$
• 循环处理 $D$ 天：每次循环都是常数操作，时间复杂度 $O(D)$
• 输出结果：$O(N)$

总体时间复杂度为 $O(N + D)$。题目保证 $N \le 1000, D \le 1000$，在 1 秒时间限制内可以轻松通过。

空间复杂度为 $O(N)$，用于存储每个罐的金额，也完全满足内存限制。

参考代码

下面是完整的 C++ 代码（与参考代码一致），并附有详细的注释说明。

cpp
复制
1#include <iostream>
2using namespace std;
3
4int jar[1000];  // 最多1000个储蓄罐
5
6int main() {
7    int n, d;
8    cin >> n >> d;
9
10    // 初始化所有储蓄罐金额为0
11    for (int i = 0; i < n; i++)
12        jar[i] = 0;
13
14    // 依次处理每一天的存款
15    for (int i = 1; i <= d; i++) {
16        int a;
17        cin >> a;          // 第 i 天选择的储蓄罐编号
18        jar[a] += i;       // 存入 i 元
19    }
20
21    // 输出结果，注意末尾不能有多余空格
22    cout << jar[0];                // 先输出第一个
23    for (int i = 1; i < n; i++)
24        cout << " " << jar[i];     // 再输出空格和后续金额
25    cout << endl;
26
27    return 0;
28}

代码说明：

• 第 4 行：定义一个全局数组 jar，大小为 1000，满足最大 $N$ 的需求。
• 第 9～10 行：读入 $N, D$。
• 第 12～13 行：将数组元素全部初始化为 0。这一步很重要，避免使用未初始化的垃圾值。
• 第 15～19 行：核心累加逻辑。i 从 1 到 $D$，恰好对应每天存入的金额；读入 a 后将 i 累加到对应下标。
• 第 22～25 行：按照格式输出。先输出第一个元素，再用 " " + 元素 的方式输出剩余元素，最后换行。这样可以避免行末出现多余空格。

总结

这道题考察了数组的简单应用和循环输入处理，是非常适合初学者的入门题目。重点在于理解下标与天数的关系，以及如何利用循环变量的值直接作为存款金额进行累加。