AtCoder ARC #185 : B - +1 and -1

ちょっと考えた。
https://atcoder.jp/contests/arc185/tasks/arc185_b

問題

整数列Aが与えられる。
i＜jとなるi,jを選び、A[i]をインクリメント、A[j]をデクリメントすることを任意回数行えるとする。
Aを単調増加にできるか判定せよ。

解法

自分は以下のようにした。
Aの先頭から値を確定していく。
A[i]以降の要素の平均値をBとする。A[i]がB以下なら、A[i]をBにできるだけ近づくように増やし、その分A[i+1]を減らそう。

というのも、値を増やしたいときに増やすのは簡単だが、減らすのは（手前の要素をさかのぼって増やさないといけないので）手間がかかる。
そこで、増やせるときに増やして問題ない程度に値を増やしておくとよい。

int T,N;
ll A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		ll S=0;
		FOR(i,N) {
			cin>>A[i];
			S+=A[i];
		}
		
		FOR(i,N-1) {
			int lef=N-i;
			ll a=S/lef;
			if(A[i]<a) {
				ll d=a-A[i];
				A[i]+=d;
				A[i+1]-=d;
			}
			S-=A[i];
		}
		
		FOR(i,N-1) if(A[i]>A[i+1]) break;
		if(i==N-1) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
}

まとめ

想定解とは違った。