Codeforces ECR #090 : F. Network Coverage

コードは簡単。
http://codeforces.com/contest/1373/problem/F

問題

円形に並んだN個の駅がある。
駅の間にはそれぞれA[i]人の人が住んでいる。
また、各駅の許容人数はB[i]人である。

各人は、家の両隣のどちらか最寄の駅を使用することにする。
各駅の許容人数を超えないよう、各人の利用する駅を割り振ることができるか？

解法

sum(A)＞sum(B)の時はそもそもなし。
それ以外の場合、適当な駅から初めて貪欲に「手前の駅に入る分だけ手前に割り振り、漏れた分は次の駅に割り振る」を2周以上試せばよい。
1周目は始めた駅の手前の人のことを考えてないのでダメだが、2周行うことでそれらも考慮される。

int T;
int N;
int A[3010101],B[3010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	FOR(x,T) {
		cin>>N;
		int mi=1<<30;
		ll sum=0;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
		}
		FOR(i,N) {
			cin>>B[i];
			sum-=B[i];
		}
		
		int lef=0;
		int ng=sum>0;
		FOR(i,2*N) {
			lef=max(0,lef)+A[i%N]-B[(i+N-1)%N];
			if(lef>B[i%N]) ng=1;
		}
		
		if(ng==0) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		
	}
}

まとめ

典型っぽいのにダメだったな…。