题解：AT_abc388_d [ABC388D] Coming of Age Celebration

xyx404 · 2025-01-12 10:07:50 · 题解

思路：

模拟。

定义一个变量 give 表示现在可以给珠子的人数，再定义一个数组 R，R_i 表示有多少人只能给到第 i 个人。

每一个成年的人在自己还要珠子的时候必须要给刚刚成年的人一个珠子，所以第 i 个人要给 n-i 个珠子，可以得到 give 个珠子，如果第 i 个人的数量加上之前成年的人给他的数量不够给后面所有的刚成年的，那么计算他能给到第几个人，更新 R 数组，并让 give 加一还要记得把 A_i 修改为 0；如果够那么 A_i 就等于他加上 give 后给减去他成年后还有多少个未成年的数量，give 也要加一。

更新完第 i 个人后让 give 减去只能给到第 i 个人的数量，也就是 R_i。

代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define itn int
#define ull unsigned long long
LL T=1;
LL n;
LL a[int(5*1e5+10)];
LL R[int(5*1e5+10)];
int main(){
//  cin>>T;
    while(T--){
        cin>>n;
        int give=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];

//          cout<<give<<"\n";
            if(a[i]-(n-i)+give<0){
                R[a[i]+give+i]++;
                a[i]=0;
            }
            else{
                a[i]=a[i]-(n-i)+give;
            }
            give++;
            give-=R[i];
            cout<<a[i]<<" ";
        }

    }
    return 0;
}