【PGBATTLE2019_かつおぶし4】距離和最小

ふつうに貪欲？でした。
3 1 4 のように間がへこんでいたり、
1 5 3 のように間が突出していたら、均すだけ。

均す値は、差の絶対値の小さい方。

・  3  1  4
dif  -2 +3
aft 3  3  4
   
・  4  1  3
dif  -3 +2
aft 4  3  3

・  1  5  3
dif  +4 -2
aft 1  3  3

実装

ll N;

int main(){
 cincout();
 
 cin >> N;
 ll A[N];
 rep(i, N) cin >> A[i];
 ll D[N] = {};
 rep(i, N-1) D[i] = A[i+1] - A[i];
 
 ll cost = 0;
 rep(i, N-2){
   if (D[i]<0 && D[i+1]>0){
     ll m=min(abs(D[i]), abs(D[i+1]));
     cost += m;
     D[i] += m;
     D[i+1] -= m;
     A[i+1] += m;
   }
   if (D[i]>0 && D[i+1]<0){
     ll m=min(abs(D[i]), abs(D[i+1]));
     cost += m;
     D[i] -= m;
     D[i+1] += m;
     A[i+1] -= m;
   }
 }
 ll ans = 0;
 rep(i, N-1) ans += abs(D[i]);
 ans += cost;
 cout << ans << endl;
}