G3003 [GESP202309 三级] 小杨的储蓄 题解

知识点：一维数组、模拟、累加。

解题思路

第i天读入被存入的储蓄罐编号x，给a[x]增加i，最后输出各储蓄罐金额。

为什么正确

每天操作在对应编号上增加规定金额，数组始终等于已执行操作后的真实余额。

易错点

罐子编号按题目从0起；同一罐子多次存款应累计而非覆盖。

复杂度

时间O(n+d)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,d,x;
    cin>>n>>d;
    vector<int>a(n);
    for(int i=1;i<=d;i++) {
        cin>>x;
        a[x]+=i;
    }
    for(int x:a)cout<<x<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。