2940 Wine Trading in Gergovia

問題概要

n個の村がある。それぞれの村でのワインの需要および供給がa[i]で与えられる。
a[i]が負の時は需要で、正の時は供給である。
a[i]をすべて足すとちょうど0になる。

このとき、すべての村に過不足なくワインを行き渡らせるために必要なワインの輸送量を求めよ。
ただし、1つのワインを1つ離れた村に運ぶ輸送量を1とする。

n≦100000かつ、答えは64bit整数の範囲に収まるものとする。

解法

左の村から順に、ワインが余っている村ではそのワインを回収し、
ワインが不足している村には持っているワインを貪欲に置いていくことを考える。

手持ちのワインがすべて正ならばこれは最適解であるが、
途中でワインの数が負になっても、絶対値を輸送量に足せば最適解である。
なぜなら、その部分だけワインの輸送が逆向きだったと思えばよいからである。

ソースコード

int main(){
	int n,t,a; long long ans;
	while(scanf("%d",&n),n){
		ans=t=0;
		rep(i,n){
			scanf("%d",&a);
			ans+=abs(t);
			t+=a;
		}
		printf("%lld\n",ans);
	}
	return 0;
}