题解：AT_abc388_d [ABC388D] Coming of Age Celebration

封面

洛谷文章链接

思路：

模拟。

定义一个变量 givegive 表示现在可以给珠子的人数，再定义一个数组 RR，RiR_i 表示有多少人只能给到第 ii 个人。

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

更新完第 ii 个人后让 givegive 减去只能给到第 ii 个人的数量，也就是 RiR_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;
}