Reach Median [Manthan, Codefest 18 B]

http://codeforces.com/contest/1037/problem/B

N個の配列Aが与えられる。(Nは奇数)
この配列の中央値をSにしたい。
ある要素を+1か-1する操作を行う時、最小何回の操作で中央値をSにできるか。

解法

http://codeforces.com/contest/1037/submission/42452613

貪欲に中央値をSにしよう。
配列Aをソートして、現状の中央値を求める。
中央がct番目であるとする。
　
A[st] = Sの場合。
この場合は既に達成できているので、0が答え。
　
A[st]＜Sの場合。
A[st]をとりあえずSにする。
これだけでは、stより後の項目でS未満のものがあれば順番が入れ替わってしまう。
そのため、[st,N)の部分でS未満の要素をSにするように貪欲に操作をする。
　
A[st]＞Sの場合。
A[st]をとりあえずSにする。
これだけでは、stより前の項目でSより大きいものがあれば順番が入れ替わってしまう。
そのため、[0,st]の部分でSより大きい要素をSにするように貪欲に操作をする。

int N, S, A[201010];
//---------------------------------------------------------------------------------------------------
ll solve() {
    sort(A, A + N);

    int ct = N / 2;

    if (A[ct] == S) return 0;
    else if (A[ct] < S) {
        ll ans = 0;
        rep(i, ct, N) if (A[i] < S) ans += S - A[i];
        return ans;
    } else {
        ll ans = 0;
        rep(i, 0, ct + 1) if (S < A[i]) ans += A[i] - S;
        return ans;
    }
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> A[i];
    cout << solve() << endl;
}