鲁的女孩 题解

题意

给两个数列，对它进行排列，使得对应两数的和的最大值最小。

题解

贪心，先将 \(a\)、\(b\) 排个序（先不考虑时间）。

将 \(a_1\) 与 \(a_n\) 匹配。

\(a_2\) 与 \(a_{n - 1}\) 匹配。

……

取最大值即可。

考虑到 \(n \le 10^5\)，不可以暴力枚举。

但是 \(a, b \le 100\)，可以开一个桶，最后统计即可。

时间复杂度 \(\mathcal O(W n)\)

（\(W\) 为 \(a,b\) 的范围，即 \(100\)）

namespace zqh {
int n;
int a[105], b[105], a2[105], b2[105];

void init() {
    cin >> n;
}

void solve() {
    while (n--) {
        int x, y;
        cin >> x >> y;
        a[x]++;
        b[y]++;
        int l = 1, r = 100;
        for (int i = 1; i <= 100; i++) {
            a2[i] = a[i];
            b2[i] = b[i];
        }
        int num = 0;
        while (l <= 100 && r >= 1) {
            while (!a2[l] && l <= 100)
                l++;
            if (l > 100)
                break;
            while (!b2[r] && r >= 1)
                r--;
            num = max(num, l + r);
            int t = min(a2[l], b2[r]);
            a2[l] -= t;
            b2[r] -= t;
        }
        cout << num << endl;
    }
}

void main() {
    init();
    solve();
}
}  // namespace zqh