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

hamayanhamayan's blog

square1001 and Permutation 2 [yukicoder No.693]

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

解説

https://yukicoder.me/submissions/264153

貪欲に揃えていくことを考える。
貪欲法で良いのかという議論もあるが、星1.5という所とコンテスト中でないという所から突っ込んだらAC。
小さい順に1,2,3,...と割り当てていく。
ソートして1,2,3,...にするときの距離の総和が答え。

int N, A[50];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);

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