はまやんはまやんはまやん

hamayanhamayan's blog

よくあるボールを移動するやつ [yukicoder 929]

https://yukicoder.me/problems/no/929

解説

https://yukicoder.me/submissions/400103

なんとなく貪欲でやれば良さそうな気がする。
先頭からなければ前から持ってくるか、後ろから持ってくるかすればいい。
これはボールに最初にある場所の添字を付けて、昇順ソートしたときの位置が最適な位置になるので、
添字とボールに付いている添字との差を取っていけば答え。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    vector<int> idx;
    rep(i, 1, N + 1) {
        int B; cin >> B;
        rep(j, 0, B) idx.push_back(i);
    }

    ll ans = 0;
    rep(i, 0, N) ans += abs(idx[i] - (i + 1));
    cout << ans << endl;
}