読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 11054 : Wine trading in Gergovia

UVa 数学 UVa

問題リンク:http://uva.onlinejudge.org/external/110/11054.html

問題概要:
n人の人がワインを売買する
人iの情報はa[i](0<=i= 0 ならその人はa[i]個のワインを買う
a[i] < 0 ならその人は-a[i]個のワインを売る
a[i]の総和は0となる
a[i]のうち任意の数を任意の場所に移動できる
その際に、abs(j-i)*(移動する数)だけコストがかかる

全てa[i]を0にする時にかかる最小のコストを求めよ

解法:
必ず全ての場所を0にする必要がある
iを0からn-1まで見ていくが、その場所は0にする必要があるのでもし現状で0でないなら残っている数を全て次へ持っていかなければならない
なんというか、左からコストを計算しながら足していくだけ
コードをみて悟ってほしい

コード;

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

int main()
{
  int n;
  while(cin >> n,n)
    {
      ll a[n];
      rep(i,n)cin >> a[i];
      ll ans = 0;
      ll cost = 0;
      rep(i,n)
	{
	  cost += a[i];
	  ans += (cost>0?cost:-cost);
	}
      cout << ans << endl;
    }
  return 0;
}