第 i 天往指定编号的存钱罐里存 i 元,求 D 天后每个罐子里有多少钱。
小杨共有 N 个储蓄罐,编号从 0 到 N − 1。从第 1 天开始,每天挑一个罐子存钱:第 i 天往编号 aᵢ 的罐子里存入 i 元钱。
过了 D 天后,请输出每个罐子里各有多少钱(按编号 0 到 N − 1 的顺序)。
数组当桶按天累加索引与编号对应格式化输出
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N、D;第二行 D 个整数 aᵢ |
| 输出 | N 个整数,编号 0 到 N − 1 的罐内金额 |
| 数据范围 | 1 ≤ N, D ≤ 1000 |
| 编号范围 | 0 ≤ aᵢ ≤ N − 1 |
| 存款规则 | 第 i 天存入 i 元 |
sum[罐号] 累加,罐号直接当下标注意每天存的金额是"第几天",不是固定的 1 元。
| 天数 i | 存入罐号 aᵢ | 存入金额 | 0 号罐 | 1 号罐 |
|---|---|---|---|---|
| 第 1 天 | 0 | 1 | 1 | 0 |
| 第 2 天 | 1 | 2 | 1 | 2 |
| 第 3 天 | 0 | 3 | 1 + 3 = 4 | 2 |
输出:4 2 ✓
| 天数 i | 罐号 | 金额 | 0 号罐 | 1 号罐 | 2 号罐 |
|---|---|---|---|---|---|
| 第 1 天 | 0 | 1 | 1 | 0 | 0 |
| 第 2 天 | 0 | 2 | 3 | 0 | 0 |
| 第 3 天 | 0 | 3 | 6 | 0 | 0 |
| 第 4 天 | 2 | 4 | 6 | 0 | 4 |
| 第 5 天 | 0 | 5 | 11 | 0 | 4 |
输出:11 0 4 ✓
读入罐号时立刻把当天的金额加上去
sum[a] += i 就完成了记账。把所有罐号存进数组,之后再逐罐统计
| 方案 | 时间复杂度 | 空间 |
|---|---|---|
| 边读边累加 | O(D) | O(N) |
| 存后统计 | O(N × D) | O(N + D) |
第一行输入 N 和 D,第二行输入 D 个罐号,程序会逐天记账并给出每罐余额。
点按钮开始 →
#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; }
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 足够 |
写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
2 3 | 4 2 | 题面样例 1 |
3 5 | 11 0 4 | 题面样例 2 |
1 1 | 1 | 只有一个罐子 |
3 2 | 0 0 3 | 1 + 2 = 3 都进了 2 号罐 |
2 2 | 1 2 | 每个罐各存一次 |
i = 0 会让第 0 天存 0 元,整个金额序列都错位。一个长度为 N 的数组记录每个罐子的余额。
✅ N、D 都只有 1000,任何写法都瞬间完成;这题考的是"天数即金额"这个细节。
// 数组当桶的计数/累加模板 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) 避免行末空格 | 所有多元素输出题 |
sum[a] += i 改成 sum[a] += 1LL * i * i,并注意用 long long 防止溢出。)