题目描述

难度分:$1400$

输入$n(1 \leq n \leq 2 \times 10^5)$和两个$1$~$n$的排列$a$，$b$。

你可以对$a$或$b$执行任意次循环右移或循环左移。输出操作后，最多有多少个$a[i]=b[i]$。

注：把$[1,2,3,4]$循环右移一次，得$[4,1,2,3]$。

输入样例$1$

5
1 2 3 4 5
2 3 4 5 1

输出样例$1$

5

输入样例$2$

5
5 4 3 2 1
1 2 3 4 5

输出样例$2$

1

输入样例$3$

4
1 3 2 4
4 2 3 1

输出样例$3$

2

算法

分组

不是很好想，一开始没有利用$a$和$b$都是排列的特性，一直陷入“字符串匹配”的思路，怎么都做不对。最后发现利用排列这个条件很容易就能解决，如果$a[i]=b[j]$成立，假想$a$的$i$位置向$b$的$j$位置连了一根线，那由于$a$中$a[i]$这个数值只有一个，$b$中$b[j]$这个数值也只有一个，所以只要把相同“斜率”（斜率定义为$k=val2pos_1[val]-val2pos_2[val]$，其中$val2pos_1[val]$表示$val$这个数值在数组$a$中的索引，$val2pos_2[val]$表示$val$这个数值在数组$b$中的索引）的线分到同一组就可以了。

由于可以对$a$数组进行旋转操作，负的斜率通过加上$n$处理成正数。所有组中，线数量的最大值就是答案。

复杂度分析

时间复杂度

遍历$a$和$b$两个数组预处理出$val2pos_1$和$val2pos_2$，再遍历一遍数组$a$进行斜率分组，时间复杂度为$O(n)$。

空间复杂度

$val2pos_1$、$val2pos_2$以及斜率分组数组$cnt$的空间消耗都是线性的，因此算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int n, a[N], b[N];

int main() {
    scanf("%d", &n);
    int val2pos1[n] = {0};
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        val2pos1[a[i]] = i;
    }
    int val2pos2[n] = {0};
    for(int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        val2pos2[b[i]] = i;
    }
    int ans = 0;
    int cnt[n] = {0};
    for(int i = 1; i <= n; i++) {
        int offset = (val2pos1[a[i]] - val2pos2[a[i]] + n) % n;
        cnt[offset]++;
        ans = max(ans, cnt[offset]);
    }
    printf("%d\n", ans);
    return 0;
}