Noelちゃんと星々 [yukicoder No.609]

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

解法

https://yukicoder.me/submissions/222652

「距離の総和を最小化するには中央値を使う」という知識がある。
これをやるだけ。
この知識は有名ではないが、今までに2回見たことがある。 参照

typedef long long ll;
int N; ll Y[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> Y[i];
    sort(Y, Y + N);

    ll c;
    if (N % 2 == 1) c = Y[N / 2];
    else c = (Y[N / 2] + Y[N / 2 - 1]) / 2;

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