PKU 2940 Wine Trading in Gergovia
http://poj.org/problem?id=2940
一直線上に等間隔にn個の家が並んでいる。いま、各家がa_i本のワインを必要としていたり、売ろうとしていたりしている。
需要と供給を満たすようにワインを移動させるとき、移動本数×移動距離の最小値はいくらかを求めるというような問題。
最初からみていって、貪欲に足したり引いたりする。
cinを使ったらTLEしたので、一部scanfに書き換えました。
main(){ int n; while(cin>>n,n){ ll ans=0; ll t; cin>>t; rep(i,n-1){ int tt; scanf("%d",&tt); ans+=llabs(t); t+=tt; } cout<<ans<<endl; } }