Solution Of AT_arc195_b [ARC195B] Uniform Sum

· · 题解

Solution

设最后我们做出来的配对是 A_x + B_y = \cdots = k。设最终的答案为 f(k)。

首先考虑什么时候一定有解。

我们观察得到，当 -1 的个数大于等于 n - 1 时一定有解，这启发我们关注 -1 的个数。

事实上，-1 的个数意味着我们所需要配对多少对使得它们的和相同。即，n 减 -1 的个数要不大于 f(k)。这是必要的。

由于只能是非负整数。那么还有一个必要条件是 k 大于 A, B 中的最大值。

这两个必要条件合在一起是充要的。

我们有 f(k) = \sum_{x + y = k} \min \{\mathrm{cntA}_x, \mathrm{cntB}_y\}。

因此可以根据这个式子开 map 记录 A, B 和答案。

最后遍历 map 判断是否存在这样一个充要的 k 就可以了。

不懂为什么有人说 map 过不去。

Code

#include <iostream>
#include <map>

using namespace std;
int n, cnt, x, mx;
map <int, int> A, B, mp;

int main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> x;
        mx = max(mx, x);
        if (x == -1) cnt ++;
        else A[x] ++; 
    }
    for (int i = 1; i <= n; i ++) {
        cin >> x;
        mx = max(mx, x);
        if (x == -1) cnt ++;
        else B[x] ++;
    }
    if (cnt >= n - 1) return cout << "Yes\n", 0;
    for (auto [i, x] : A) 
    for (auto [j, y] : B) {
        mp[i + j] += min(x, y);
    }
    for (auto [p, q] : mp) {
        if (q >= n - cnt && p >= mx) 
            return cout << "Yes\n", 0;
    }
    cout << "No\n";
    return 0;
}