题解

题目解析

• 输入输出：第一行输入两个整数 $N$（储蓄罐数量，编号 $0$ 到 $N-1$）和 $D$（总天数）。第二行输入 $D$ 个整数 $a_i$，表示第 $i$ 天往编号为 $a_i$ 的储蓄罐存钱。输出 $N$ 个整数，第 $i$ 个整数表示编号为 $i-1$ 的储蓄罐中的总金额（即按 $0,1,\dots,N-1$ 的顺序输出）。
• 数据范围：$1 \le N \le 1000$，$1 \le D \le 1000$，所有 $a_i$ 满足 $0 \le a_i \le N-1$。
• 复杂度要求：需遍历 $D$ 天记录，时间复杂度 $O(D)$，空间复杂度 $O(N)$，远低于 $1\text{s}$ 和 $128\text{MB}$ 限制。
• 算法知识点：简单模拟、数组统计、单点累加

思路解析

1. 建立储蓄罐账户：创建一个大小为 $N$ 的数组 arr（初始化为0），数组下标对应储蓄罐编号，值对应该储蓄罐的累计金额。代码中数组开至 $2000$ 以确保不越界。
2. 按天处理存款：关键观察是第 $i$ 天存入的金额恰好为 $i$ 元（而非固定金额）。遍历天数 $i$ 从 $1$ 到 $D$，读入当天目标储蓄罐编号 $x$，执行 arr[x] += i，将 $i$ 元累加到对应储蓄罐。
3. 顺序输出余额：最后顺序遍历编号 $0$ 到 $N-1$，输出每个 arr[i] 即为该储蓄罐的最终金额。

完整代码

#include <bits/stdc++.h>
using namespace std;

int arr[2000];  // 储蓄罐金额统计，arr[i]表示编号i的储蓄罐中的总金额

int main() {
    int n, m;  // n:储蓄罐数量N, m:天数D
    cin >> n >> m;
    // 遍历第1天到第m天，第i天存入i元钱
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;      // 读入第i天选中的储蓄罐编号
        arr[x] += i;   // 关键：第i天存入的金额是i元，累加到对应储蓄罐
    }
    // 按编号0到n-1顺序输出每个储蓄罐的累计金额
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}