笔试时间：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] = i

for 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;
    }