题解：AT_arc195_b [ARC195B] Uniform Sum

2huk · 2025-03-25 17:31:05 · 题解

令 f(z) 表示最多能找到多少个对 (i, j) 使得 a_i + b_j = z，且每个对的 i 互不相同，j 互不相同。比如当 a=[1,1],b=[2,2] 时 f(3)=2。

令数组 a 中 -1 的个数为 c_a，数组 b 中 -1 的个数为 c_b。

如果最终我们希望 a_1+b_1=a_2+b_2=\dots=z，首先我们会尽可能多地将已经确定的数字（不是 -1 的数字）配对，这样总共会配成 f(z) 个对。

此时数组 a 中还剩于有 c_a 个 -1 和 n-c_a-f(z) 个非 -1，数组 b 中有 c_b 个 -1 和 n-c_b-f(z) 个非 -1。现在这些非 -1 的数已经没法两两配对了（因为上一步匹配完了），因此每个非 -1 的数都会找一个 -1 进行配对。于是 z 合法等价于 c_a \ge n-c_b-f(z) 且 c_b \ge n-c_a-f(z)。

当然，因为 -1 不能替换为负数，所以 z \ge \max(a_1,a_2,\dots,a_n,b_1,b_2,\dots,b_n) 是必要的。

首先特判掉一个特殊情况：如果 c_a \ge n -c_b 且 c_b \ge n-c_a（即 f(z) =0），那么直接输出 Yes。这个的含义是，每个非 -1 的数都能找到一个 -1 配对。显然这样是可以构造的，把 z 取到非常大即可。

现在我们只需要求解所有 f(z),0 \le z \le 2\times 10^9 就好了。全求出来显然不可能，但显然满足 f(z) \ne 0 的 z 是 n^2 级别的。这样复杂度就对了。

但是怎样快速的求出这 n^2 个 f(z) 的值呢？首先将 a,b 放到桶里，令 A_x 表示 a 中 x 的出现次数，B_x 表示 b 中 x 的出现次数，n^2 枚举 i,j，将 f(i+j) 加上 \min(A_i,B_j) 即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 2010;

int n, a[N], b[N];
unordered_map<int, int> A, B, f;

signed main() {
    cin >> n;

    int mx = 0;
    for (int i = 1; i <= n; ++ i ) {
        cin >> a[i];
        A[a[i]] ++ ;
        mx = max(mx, a[i]);
    }

    for (int i = 1; i <= n; ++ i ) {
        cin >> b[i];
        B[b[i]] ++ ;
        mx = max(mx, b[i]);
    }

    for (auto [i, x] : A)
        if (i != -1)
            for (auto [j, y] : B)
                if (j != -1)
                    f[i + j] += min(x, y);

    if (A[-1] >= n - B[-1]) {
        cout << "Yes\n";
        return 0;
    }

    for (auto [i, x] : f)
        if (i >= mx && A[-1] >= n - B[-1] - x) {
            cout << "Yes\n";
            return 0;
        }

    cout << "No\n";

    return 0;
}