POJ 2940 - Wine Trading in Gergovia

http://poj.org/problem?id=2940

概要

1本の道に等間隔に家が n 個並んでいて，i 番目の家は

• a[i] >= 0 なら，a[i] 本のワインを買おうとしている．
• a[i] < 0 なら，a[i] 本のワインを売ろうとしている．

需要の合計と供給の合計は一致しているとする．

i 番目の家から j 番目の家にワインを売りに行くには |i - j| のコストがかかるとして，このコストの最小値を答える．

制約

• 2 <= n <= 100000
• -1000 <= a[i] <= 1000
• a[i] の合計値は 0

解法

貪欲っぽく i 番目の要求を満たすように i+1 番目のワインを移動させる，というのを i = 0 .. n-2 について行って，移動させたワインの本数分を足し合わせていったものが答え．

 1 #include <cstdio>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6   int N;
 7   while (scanf("%d", &N) != EOF && N != 0) {
 8     long long ans = 0LL, acc = 0LL;
 9     scanf("%lld", &acc);
10     for (int i = 1; i < N; i++) {
11       int a;
12       scanf("%d", &a);
13       ans += acc < 0 ? -acc : acc;
14       acc += a;
15     }
16     printf("%lld\n", ans);
17   }
18   return 0;
19 }