UVa 11054 : Wine trading in Gergovia
問題リンク:http://uva.onlinejudge.org/external/110/11054.html
問題概要:
n人の人がワインを売買する
人iの情報はa[i](0<=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; }