GESP 题解库 / 3 级题解 / [GESP202309 三级] 小杨的储蓄 · 第 21 / 28 题
GESP202309 三级 · B3867 · 入门

小杨的储蓄

第 i 天往指定编号的存钱罐里存 i 元,求 D 天后每个罐子里有多少钱。

📊
N, D ≤ 1000
数据规模
🔢
int
数值类型
⚡
O(D)
时间复杂度
🎯
数组当桶累加
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小杨共有 N 个储蓄罐,编号从 0 到 N − 1。从第 1 天开始,每天挑一个罐子存钱:第 i 天往编号 aᵢ 的罐子里存入 i 元钱。

过了 D 天后,请输出每个罐子里各有多少钱(按编号 0 到 N − 1 的顺序)。

💡
人话翻译:这是一道"记账"题。关键是记住第 i 天存的是 i 元(不是每天 1 元!),所以天数越大存得越多。用一个数组按罐号累加即可。

🔍 关键词提取

数组当桶按天累加索引与编号对应格式化输出

已知条件

项目说明
输入第一行 N、D;第二行 D 个整数 aᵢ
输出N 个整数,编号 0 到 N − 1 的罐内金额
数据范围1 ≤ N, D ≤ 1000
编号范围0 ≤ aᵢ ≤ N − 1
存款规则第 i 天存入 i 元

需要解决的问题

02
思维导图
整理解题思路的全貌
🏦 数组当账本
📥 读入
读 N、D
读 D 个罐号 aᵢ
罐号范围 0 ~ N−1
天数从 1 开始数
💰 累加
第 i 天存 i 元
sum[aᵢ] 加上 i
i 从 1 到 D
注意不是每天 1 元
🖨️ 输出
按罐号 0 ~ N−1 输出
空格分隔
0 号罐在最前
行末不加空格
⚠️ 易错点
把存款额当成 1
天数从 0 数
输出按存钱顺序
数组下标越界
03
样例手算推导
样例两组逐天记账

🧮 样例 1:N = 2、D = 3,存钱顺序 0、1、0

注意每天存的金额是"第几天",不是固定的 1 元。

天数 i存入罐号 aᵢ存入金额0 号罐1 号罐
第 1 天0110
第 2 天1212
第 3 天031 + 3 = 42
🔑
0 号罐为什么是 1 + 3 = 4?因为第 1 天和第 3 天都存进了 0 号罐,而金额分别是 1 元和 3 元。存钱的"金额"跟着天数走,这是本题的核心。

输出:4 2 ✓

🧮 样例 2:N = 3、D = 5,存钱顺序 0、0、0、2、0

天数 i罐号金额0 号罐1 号罐2 号罐
第 1 天01100
第 2 天02300
第 3 天03600
第 4 天24604
第 5 天051104

输出:11 0 4 ✓

💡
1 号罐一直是 0:因为 D 天里从来没往 1 号罐存过钱,所以它输出 0。别忘了输出没有被存过的罐子。
04
解法对比
数组累加 vs 逐天回溯统计

⚔️ 解法对比

🟢 数组边读边累加(推荐) 推荐

读入罐号时立刻把当天的金额加上去

  • 时间 O(D)
  • 空间 O(N)
  • 一遍读取完成
  • 不需要保存所有罐号
💡
为什么推荐:读第 i 个数时,当天的金额 i 是已知的,直接 sum[a] += i 就完成了记账。

🟠 先存罐号再统计

把所有罐号存进数组,之后再逐罐统计

  • 需要额外 O(D) 空间
  • 要写两重循环
  • 复杂度更差
  • 没必要
⚠️
注意:如果按罐号逐个去扫描所有天,复杂度会变成 O(N × D),本题数据小还不至于超时,但写法明显更差。

📈 性能对比

方案时间复杂度空间
边读边累加O(D)O(N)
存后统计O(N × D)O(N + D)
05
算法流程图
读一天、记一笔
开始读入 N、D;数组 sum[0..N−1] 全部置 0i 从 1 到 D读入罐号 a;sum[a] 加上 iD 天都记完了吗?按罐号 0 到 N−1 输出 sum结束还有一天 → i 加 1
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🏦 储蓄罐记账器

第一行输入 N 和 D,第二行输入 D 个罐号,程序会逐天记账并给出每罐余额。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

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

int sum[1005];

int main() {
    int N, D;
    scanf("%d %d", &N, &D);

    for (int i = 1; i <= D; i++) {      // i 既是天数,也是当天存入的金额
        int a;
        scanf("%d", &a);
        sum[a] += i;                     // 罐号直接当下标
    }

    for (int i = 0; i < N; i++) {
        if (i) printf(" ");
        printf("%d", sum[i]);
    }
    printf("\n");
    return 0;
}
🔑
为什么循环变量 i 直接当金额用?题目说"第 i 天存入 i 元",所以把循环写成 for (int i = 1; i <= D; i++) 后,i 恰好就是当天的金额,一个变量身兼两职,代码非常简洁。

📖 关键几行怎么看

代码作用为什么这样写
for (i = 1; i <= D; i++)遍历每一天从 1 开始,因为第 1 天存 1 元
sum[a] += i记账罐号直接当下标,金额就是 i
if (i) printf(" ")控制空格第一个数前面不输出空格
int sum[1005]全局数组自动清零N ≤ 1000,开到 1005 足够
⚠️
三个坑:① 把每天的金额当成 1 元(最常见的误解);② 输出时按"存钱顺序"而不是按"罐号顺序";③ 数组只开了 N 大小却访问了下标 N − 1 之外的(本题保证不会)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
2 3
0 1 0
4 2题面样例 1
3 5
0 0 0 2 0
11 0 4题面样例 2
1 1
0
1只有一个罐子
3 2
2 2
0 0 31 + 2 = 3 都进了 2 号罐
2 2
0 1
1 2每个罐各存一次
✅
自查清单:① 第 i 天存的是 i 元吗?② 输出按罐号顺序吗?③ 没被存过的罐子输出了 0 吗?

🚨 易错点清单

⚠️
把金额当成 1:那样样例 1 会输出 "2 1",与正确答案 "4 2" 不符。金额必须等于天数。
⚠️
输出顺序错:必须按罐号 0、1、…、N−1 依次输出,不能按存钱的先后顺序。
⚠️
循环从 0 开始:写成 i = 0 会让第 0 天存 0 元,整个金额序列都错位。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N + D)
空间复杂度
O(N)
N, D 最大
1000
运算量
2000 次

时间怎么算的?

空间都用在哪?

一个长度为 N 的数组记录每个罐子的余额。

✅ N、D 都只有 1000,任何写法都瞬间完成;这题考的是"天数即金额"这个细节。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 数组当桶的计数/累加模板
int cnt[1005];              // 求次数
long long sum[1005];        // 求和(金额可能较大时用 long long)

// 读入同时累加(最常用)
for (int i = 1; i <= D; i++) {
    int a; scanf("%d", &a);
    cnt[a]++;
    sum[a] += i;
}

// 输出时控制空格的标准写法
for (int i = 0; i < N; i++) {
    if (i) printf(" ");
    printf("%lld", sum[i]);
}
printf("\n");

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
数组当桶累加用下标作为"键"累加计数排序、词频统计、分组求和
索引直接映射罐号 0 ~ N−1 与数组下标一一对应所有编号从 0 开始的题目
输出格式控制用 if (i) 避免行末空格所有多元素输出题
🌟
思考题:如果题目改成"第 i 天存入的是 i² 元",代码要改哪一处?(提示:只需把 sum[a] += i 改成 sum[a] += 1LL * i * i,并注意用 long long 防止溢出。)