You are given two arrays a and b both of length n. You will merge† these arrays forming another array c of length 2⋅n. You have to find the maximum length of a subarray consisting of equal values across all arrays c that could be obtained. † A merge of two arrays results in an array c composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c. We repeat this operation as long as we can (i.e. at least one array is nonempty). Input Each test contains multiple test cases. The first line of input contains a single integer t (1≤t≤104) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer n (1≤n≤2⋅105) — the length of the array a and b. The second line of each test case contains n integers a1,a2,…,an (1≤ai≤2⋅n) — the elements of array a. The third line of each test case contains n integers b1,b2,…,bn (1≤bi≤2⋅n) — the elements of array b. It is guaranteed that the sum of n across all test cases does not exceed 2⋅105. Output For each test case, output the maximum length of a subarray consisting of equal values across all merges. c++实现
时间: 2024-02-04 18:04:30 浏览: 192
java 源码分析Arrays.asList方法详解
这道题可以用哈希表来解决。首先将两个数组合并并排序,然后从小到大遍历排序后的数组,对于每个元素,记录它在两个数组中出现的位置,如果两个位置不一样,说明这个元素在两个数组中出现了,将这个元素加入哈希表中,并记录它在两个数组中出现的位置。最后,遍历哈希表,找到相邻位置差最大的元素,它们构成的子数组就是所有合并中的相等值组成的最大子数组。
具体实现可以参考以下代码:
```c++
#include <iostream>
#include <unordered_map>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
vector<int> c;
c.insert(c.end(), a.begin(), a.end());
c.insert(c.end(), b.begin(), b.end());
sort(c.begin(), c.end());
unordered_map<int, pair<int, int>> mp;
int ans = 0;
for (int i = 0; i < 2 * n; i++) {
if (i > 0 && c[i] == c[i - 1]) {
continue;
}
int j = i + 1;
while (j < 2 * n && c[j] == c[i]) {
j++;
}
j--;
if (j - i + 1 > ans) {
ans = j - i + 1;
}
mp[c[i]] = make_pair(lower_bound(a.begin(), a.end(), c[i]) - a.begin(), lower_bound(b.begin(), b.end(), c[i]) - b.begin());
i = j;
}
for (auto [k, v] : mp) {
ans = max(ans, abs(v.first - v.second) + 1);
}
cout << ans << endl;
}
return 0;
}
```
阅读全文