题解：CF1976C Job Interview

2huk · 2024-06-18 16:47:44 · 题解

显然枚举 i 表示这个人没了。

思考若没有

如果该岗位已经招满了，就把 i 分配到另一岗位上。

的规则，显然我们会选择 i 更适合的岗位。

有这个限制后，一定也存在一个最长前缀 [1, j] 表示这些人是按照自己适合的选的。也就是说，在这些人参与招聘时，两个岗位都未招满。

我们可以二分这个前缀长度 j。显然 [1, j] 结束后，一定存在一个岗位招满了。那么 [j+1, n+m+1] 就只能在另一个没有招满的岗位上工作了。

具体实现上需要维护若干个前/后缀和。见代码。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 400010;

int n, m, a[N], b[N], sum[N], pre[N], A[N], B[N];

void solve() {
    cin >> n >> m;

    for (int i = 1; i <= n + m + 1; ++ i ) cin >> a[i];
    for (int i = 1; i <= n + m + 1; ++ i ) cin >> b[i];

    for (int i = 1; i <= n + m + 1; ++ i ) sum[i] = sum[i - 1] + (a[i] > b[i]);
    for (int i = 1; i <= n + m + 1; ++ i ) pre[i] = pre[i - 1] + max(a[i], b[i]);

    A[n + m + 2] = B[n + m + 2] = 0;
    for (int i = n + m + 1; i; -- i ) A[i] = A[i + 1] + a[i], B[i] = B[i + 1] + b[i];

    for (int i = 1; i <= n + m + 1; ++ i ) {
        int l = 0, r = n + m + 1, pos = -1;
        int P, Q;

        while (l <= r) {
            int mid = l + r >> 1;

            int p = sum[mid], q = mid - p;
            if (mid >= i) (a[i] > b[i] ? p : q) -- ;

            if (p >= n || q >= m) {
                P = p, Q = q;
                r = mid - 1, pos = mid;
            }
            else {
                l = mid + 1;
            }
        }

        int res = pre[pos] - (pos >= i ? max(a[i], b[i]) : 0ll);
        res += Q == m ? A[pos + 1] - (pos + 1 <= i ? a[i] : 0) : B[pos + 1] - (pos + 1 <= i ? b[i] : 0);

        cout << res << ' ';
    }

    cout << '\n';
}

signed main() {
    int T;
    cin >> T;
    while (T -- ) solve();
    return 0;
}