笔试时间：2023年9月10日 秋招  第一题  题目  小红有一个长度为n的排列p，其中1到n的每个数都恰好出现一次，pos[i]表示排列中元素i的下标。例如p=[3,2,4,5,1],则pos =[5,2,1,3,4]。还有一个长度为m的数组a，数组的元素互不相同，即ai!=aj,。如果满足pos[ai]<pos[ai+1]<=pos[ai]+d,则认为a是一个优秀的数组。现在给定长度为n的排列p，以及长度为m的数组a1,a2...am，小红想知道最少需要多少次操作可以将数组变的不优秀，每次操作可以交换排列p的相邻元素，对应的pos数组也会发生变化。  输入描述  一行三个整数n,m,d，表示排列的长度，数组的长度以及d的值。  一行n个整数p1，p2，...,pn，表示排列p。  一行m个整数a1,a2,...am,表示数组a。  2≤m≤n≤10^5  输出描述  输出一个整数表示最少需要多少次操作。  样例输入     5 2 2   3 2 4 5 1   3 4    样例输出     1    说明  只需要交换4，5得到p=[3,2,5,4,1],这样a=[3,4]就不是优秀数组了。  参考题解  记录数组p中每个数的下标，然后遍历a数组，查出来a数组连续两个数在p数组中的下标，然后计算破坏他们的优秀关系需要的次数即可。互相远离：(p1 + d + 1-p2)，互相接近：(p2-p1)。  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <vector>#include <map>#include <algorithm>using namespace std;int main() {    int n, m, d;    cin >> n >> m >> d;    vector<int> elements(m + 1);    map<int, int> positions;    for (int i = 1; i <= n; i++) {        int element;        cin >> element;        positions[element] = i;    }    for (int i = 1; i <= m; i++) {        cin >> elements[i];    }    int minDifference = INT_MAX;    for (int i = 1; i < m; i++) {        int element1 = elements[i];        int position1 = positions[element1];        int element2 = elements[i + 1];        int position2 = positions[element2];        int diff1 = position2 - position1 - 1;        int diff2 = min(position1 + d - 1, n - position2) + 1;        int currentDifference = min(diff1, diff2);        minDifference = min(currentDifference, minDifference);    }    cout << minDifference << endl;    return 0;}  Java：[此代码未进行大量数据的测试，仅供参考]  import java.util.*;class DisjointSetProblem {    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        int m = scanner.nextInt();        int d = scanner.nextInt();        int[] elements = new int[m + 1];        Map<Integer, Integer> positions = new HashMap<>();        for (int i = 1; i <= n; i++) {            int element = scanner.nextInt();            positions.put(element, i);        }        for (int i = 1; i <= m; i++) {            elements[i] = scanner.nextInt();        }        int minDifference = Integer.MAX_VALUE;        for (int i = 1; i < m; i++) {            int element1 = elements[i];            int position1 = positions.get(element1);            int element2 = elements[i + 1];            int position2 = positions.get(element2);            int diff1 = position2 - position1 - 1;            int diff2 = Math.min(position1 + d - 1, n - position2) + 1;            int currentDifference = Math.min(diff1, diff2);            minDifference = Math.min(currentDifference, minDifference);        }        System.out.println(minDifference);    }}  Python：[此代码未进行大量数据的测试，仅供参考]  n, m, d = map(int, input().split())elements = [0] * (m + 1)positions = {}for i in range(1, n + 1):    element = int(input())    positions[element] = ifor i in range(1, m + 1):    elements[i] = int(input())min_difference = float('inf')for i in range(1, m):    element1 = elements[i]    position1 = positions[element1]    element2 = elements[i + 1]    position2 = positions[element2]    diff1 = position2 - position1 - 1    diff2 = min(position1 + d - 1, n - position2) + 1    current_difference = min(diff1, diff2)    min_difference = min(current_difference, min_difference)print(min_difference)  第二题  题目  小红有一个长度为n的数组a，小红可以对数组a进多次操作。每次操作，使每个数，ai加上i，例如数组[1,1,4,5,1,4]，操作一次后变成 [2,3,7,9,6,10]。现在小红想要最少的操作次数使的数组a变为严格升序，这个最少的操作次数是多少？数组a严格升序，需要满足 a1 <a2 < a3 <...< an。  输入描述  第一行输入一个整数n。  第二行输入n个整数ai。  1<=n,ai<=10^5  输出描述  输出一个整数  样例输入     6   1 1 4 5 1 4    样例输出     5    说明  5次操作后数组变成[6,11,19,25,26,34].  参考题解  经典二分做法。  C++：[此代码未进行大量数据的测试，仅供参考]  #include <iostream>#include <vector>using namespace std;int n;vector<int> a;bool check(int i) {    for (int j = 1; j < n; j++) {        long long a1 = a[j] + (long long)i * j;        long long a2 = a[j + 1] + (long long)i * (j + 1);        if (a1 >= a2) return false;    }