[Atcoder] ABC 181 E – Transformable Teacher

2020年12月12日

問題

方針

\( H, W \) を昇順に並び替えても一般性は失われないので、昇順に並び替えます。例えば、\( 2n \) 人の児童の最適なペアは

\[ (1, 2), (2, 3), \cdots , (2n – 1, n)\]

であると考えられます。これを問題に当てはめて考えると、\( N \) 人の児童のうち、\( 1 \) 人は先生とペアを組む必要があります。ここで、先生と組む児童を \( i \) とします。\( |H_i – W_j| \) を最小化する \( j \) は二分探索で求めることができます。

\( i \) が奇数であるとき

このとき、園児は

\[ (1, 2), (2, 3), \cdots, (i – 2, i – 1), (i + 1, i + 2), \cdots , (N – 1, N)\]

とグループ分けできます。したがって、先頭からの園児のペアを作ったときの累積和と、後ろから園児のペアを作ったときの累積和を計算しておくと高速に計算できます。

\( i \) が偶数であるとき

このとき、園児は

\[ (1, 2), (2, 3), \cdots, (i – 1, i + 1),  \cdots , (N – 1, N)\]

とグループ分けできます。このとき先生の添え字を \( j \) として、\( i – 1, i, i + 1, j \) でペアを作りなおした時、

\[ (i – 1, j), (i, i + 1)\]

または、

\[ (i – 1, i), (i + 1, j)\]

とペアを作った方が最適なので、\( i \) が偶数であるときは不適だと分かります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int N, M;
ll H[200000], W[200000];

int bs1(ll v) {
    int l = -1;
    int r = M;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (W[m] <= v) {
            l = m;
        } else {
            r = m;
        }
    }
    return l;
}

int bs2(ll v) {
    int l = -1;
    int r = M;
    while (r - l > 1) {
        int m = l + (r - l) / 2;
        if (v <= W[m]) {
            r = m;
        } else {
            l = m;
        }
    }
    return r;
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> H[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> W[i];
    }
    sort(H, H + N);
    sort(W, W + M);
    int n = N / 2;
    ll a[n]{};
    ll b[n]{};
    for (int i = 0; i < n; i++) {
        a[i] = H[2 * i + 1] - H[2 * i];
        b[i] = H[N - 1 - (2 * i)] - H[N - 1 - (2 * i + 1)];
    }
    ll c[n + 1]{};
    ll d[n + 1]{};
    for (int i = 0; i < n; i++) {
        c[i + 1] = c[i] + a[i];
        d[i + 1] = d[i] + b[i];
    }
    ll best = LLONG_MAX;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            int id1 = i / 2;
            ll t = c[id1] + d[n - id1];
            ll k = LLONG_MAX;
            int id2 = bs1(H[i]);
            if (0 <= id2 && id2 < M) {
                k = min(k, abs(H[i] - W[id2]));
            }
            id2 = bs2(H[i]);
            if (0 <= id2 && id2 < M) {
                k = min(k, abs(H[i] - W[id2]));
            }
            best = min(best, t + k);
        }
    }
    cout << best << "\n";
    return 0;
}