题目大意

题目要求求出最多有多少个关卡两个人互相不会嘲笑,也就是当我们求出差分数组(增量)之后，转化为求两个差分数组中相同部分的最长连续子数组。

什么是两个数组相同部分的连续子数组？

假设下标索引$i$到$j$是数组$a$和数组$b$相同部分的连续子数组，那么对于每一个$x(i<=x<=j)$,$a_x==b_x$都是成立的。

例如这两个数组

a = [1, 2, 3, 4, 5, 6, 7]
b = [0, 2, 3, 4, 9, 6, 8]

索引 $[1, 3]$, a的子数组为 $[2, 3, 4]$ 和b的子数组为$[2, 3, 4]$ 相同，是最长的连续相同部分。

索引$[5,5]$也是符合的，但是比[1,3]要短。

思路分析

1.计算增量(差分数组)

将原始数组转换为查找最长连续相同子数组的问题。我们将数组$a,b$转化为差分数组diff_a,diff_b。

2.使用双指针(滑动窗口)高效查找

通过left 和 right 指针的移动，快速确定数组diff_a和diff_b最长的连续相同区间。

将left,right初始化都为0,left 和 right 两个指针分别表示当前窗口的左右边界。 让 right 不断向右扩展，直到 diff_a[right] != diff_b[right]。 计算当前连续相等子区间的长度 right - left，并更新最大值 ans。 移动 left 到 right + 1 继续寻找下一个可能的连续区间。

3.输出答案

我们为什么要输出ans+1，因为我们记录的是right - left的最大值，表示left到right的差分数组都相等，题目要求我们输出选择的最多关卡，我们需要选取left到right+1的关卡，我们才能得到left到right的差分数组

时间复杂度分析

计算差分数组：$O(n)$

使用滑动窗口遍历 diff_a 和 diff_b：$O(n)$

总时间复杂度：$O(n)$

最后贴上我们的python完整代码给大家参考

代码

python代码

n = int(input())  # 读入关卡数
# 读入两个数组 arr 和 brr
arr = list(map(int , input().split()))
brr = list(map(int , input().split()))

# 计算差分数组
diff_a = []
for i in range(n - 1):
    diff_a.append(arr[i + 1] - arr[i])
    
diff_b = []
for i in range(n - 1):
    diff_b.append(brr[i + 1] - brr[i])

# 滑动窗口方法
left = 0
right = 0
ans = 0
m = len(diff_a)  # 差分数组的长度

while left < m:
    # 右指针移动到相等区间的最右边
    while right < m and diff_a[right] == diff_b[right]:
        right += 1
    # 计算该区间的长度
    ans = max(ans , right - left)
    # 左指针移动到右指针的位置，开始新的检查
    left = right + 1
    right = left

# 输出最大长度加 1（因为差分数组少一个元素）
print(ans + 1)

c++代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;  // 读入关卡数
    
    // 读入两个数组 arr 和 brr
    vector<int> arr(n), brr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> brr[i];
    }

    // 计算差分数组
    vector<int> diff_a(n - 1), diff_b(n - 1);
    for (int i = 0; i < n - 1; ++i) {
        diff_a[i] = arr[i + 1] - arr[i];
        diff_b[i] = brr[i + 1] - brr[i];
    }

    // 滑动窗口方法
    int left = 0, right = 0, ans = 0;
    int m = diff_a.size();

    while (left < m) {
        // 右指针移动到相等区间的最右边
        while (right < m && diff_a[right] == diff_b[right]) {
            right++;
        }
        // 计算该区间的长度
        ans = max(ans, right - left);
        // 左指针移动到右指针的位置，开始新的检查
        left = right + 1;
        right = left;
    }

    // 输出最大长度加 1（因为差分数组少一个元素）
    cout << ans + 1 << endl;

    return 0;
}

java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();  // 读入关卡数

        // 读入两个数组 arr 和 brr
        int[] arr = new int[n];
        int[] brr = new int[n];
        for (int i = 0; i < n; ++i) {
            arr[i] = sc.nextInt();
        }
        for (int i = 0; i < n; ++i) {
            brr[i] = sc.nextInt();
        }

        // 计算差分数组
        int[] diff_a = new int[n - 1];
        int[] diff_b = new int[n - 1];
        for (int i = 0; i < n - 1; ++i) {
            diff_a[i] = arr[i + 1] - arr[i];
            diff_b[i] = brr[i + 1] - brr[i];
        }

        // 滑动窗口方法
        int left = 0, right = 0, ans = 0;
        int m = diff_a.length;

        while (left < m) {
            // 右指针移动到相等区间的最右边
            while (right < m && diff_a[right] == diff_b[right]) {
                right++;
            }
            // 计算该区间的长度
            ans = Math.max(ans, right - left);
            // 左指针移动到右指针的位置，开始新的检查
            left = right + 1;
            right = left;
        }

        // 输出最大长度加 1（因为差分数组少一个元素）
        System.out.println(ans + 1);

        sc.close();
    }
}

本题为2024年8月28日得物机考原题

得物机考的介绍点击这里

题目内容

小红和小堡正在玩一个游戏，每一关都有一个分数。如果某人某一关分数比上一关高，但另一个人这一关分数比上一关低，那么他就可以嘲笑对方。如果两个人这一关游戏的分数都比上一关多，则增量更多的可以嘲笑对方;如果两个人这一关游戏的分数都比上一关少，则减量更少的可以嘲笑对方。只有当他们的增量相同或者减量相同时，才不会互相嘲笑。

例如，假设小红第一关的分数为$2$，第二关的分数为$8$;小堡第一关的分数为$5$，第二关的分数为$10$，显然小红增加的比小堡多，那么小红就可以嘲笑小堡。

现在给定了小红和小堡每一关的分数，你可以选择一段连续的关卡，使得一段关卡中两个人都不会互相嘲笑，问最多可以选择多少个关卡。特别的一段连续关卡中的第一关两人不会互相嘲笑。

输入描述

第一行输入一个正整数$n$,代表关卡数。

第二行输入$n$个整数$a_i$,代表小红每一关的分数。

第三行输入$n$个整数$b_i$,代表小堡每一关的分数。

$2≤n≤10^5$

$-10≤a_i，b_i≤10^9$

输出描述

输出可以选择最多的关卡数。

示例1

输入

5
1 2 3 1 3
-1 0 3 -1 1

输出

2

说明

可以选择前两个数，$[1,2]$和$[-1,0]$相似，长度为$2$. 选择后两个数也是可以的。