P9633 题解

_Gabriel_ · 2023-09-25 22:37:09 · 题解

大意

给定两个数组 a 和 b，需要找到一个整数 ans，它表示在数组 a 中找到一个子数组，使得这个子数组包含数组 b 中的尽可能多的元素。然后，如果无法找到这样的子数组输出 Impossible，否则输出 ans 的值。

思路

先把 a 数组和 b 数组排好序，以便后续的二分查找。

使用二分查找 upper_bound 和 lower_bound 来找到数组 a 中与 b[i] 相等或者比它稍大的元素的位置。然后计算这两个位置之间的距离，即长度 len。

更新 ans，将其设置为当前 ans 和 len 中的较大值。

最后判断 ans 是否为 0，如果为 0，就是无法找到满足条件的子数组，输出 Impossible。否则，输出答案 ans。

代码

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

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 5e6 + 10;
int a[N], b[N];
int n, m, t, ans;

int main() {
    cin >> t;
    while (t--) {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        for (int i = 1; i <= m; i++) {
            cin >> b[i];
        }
        b[0] = -INF, b[m + 1] = INF;
        sort(a + 1, a + n + 1);
        sort(b, b + m + 1);
        for (int i = 0; i <= m; i++) {
            int pos1 = upper_bound(a + 1, a + n + 1, b[i]) - a;
            int pos2 = lower_bound(a + 1, a + n + 1, b[i + 1]) - a - 1;
            int len = pos2 - pos1 + 1;
            ans = max(ans, len);
        }
        if (ans == 0) {
            cout << "Impossible\n";
        } else {
            cout << ans << "\n";
        }
        ans = 0;
    }
    return 0;
}