↓ 跳过正文
题解：AT_abc388_d [ABC388D] Coming of Age Celebration

题解：AT_abc388_d [ABC388D] Coming of Age Celebration

xyx404
作者
xyx404
Have a nice day.
目录

封面

洛谷文章链接

思路：
#

模拟。

定义一个变量 $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;
}