自动搬运

查看原文

来自洛谷，原作者为

	Gabriel 登高必自卑，行远必自迩

搬运于2025-08-24 22:50:17，当前版本为作者最后更新于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;
}