• 做项目（多个C++、Java、Go、测开、前端项目）
• 刷算法（两个月高强度学算法）
• 背八股（40天挑战高频面试题）

优秀数组

题目链接 (opens new window)

解题思路

1、初始分析

• 给定一个排列 p，我们首先构建一个 pos 数组，使得 pos[i] 表示 i 在排列 p 中的位置。
• 我们需要判断数组 a 是否是一个优秀数组，即 pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d 对于所有 i 都成立。
• 我们的目标是通过最少的相邻元素交换，使得数组 a 不再是一个优秀数组。

2、思路

• 要使数组 a 不再是优秀数组，我们只需要打破条件 pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d 中的某一个。
• 一种简单的做法是让 pos[a[i]] 和 pos[a[i+1]] 之间的距离超过 d，或者直接让 pos[a[i]] >= pos[a[i+1]]。

3、具体方法

• 只需要考虑 a 中相邻元素的顺序，并判断如何交换 p 中相邻元素使得其顺序被打破。
• 假设我们需要在 p 中交换某些元素来实现上述目标，那么最小的交换次数是将 a[i] 和 a[i+1] 的位置交换。
• 如果 pos[a[i]] + 1 == pos[a[i+1]]，则需要一步交换。

4、特别情况

• 还需要考虑，如果通过交换相邻元素无法解决问题的情况。比如 pos[a[i+1]] 的位置无法移到 pos[a[i]] 的前面或超过 d。

C++代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    int n, m, d;
    cin >> n >> m >> d;

    vector<int> p(n + 1);
    vector<int> pos(n + 1);

    // 读取排列 p，并构建位置数组 pos
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        pos[p[i]] = i;
    }

    vector<int> a(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }

    int min_operations = INT_MAX;

    // 遍历数组 a 的相邻元素
    for (int i = 0; i < m - 1; i++) {
        int current_pos = pos[a[i]];
        int next_pos = pos[a[i + 1]];

        // 检查 pos[a[i]] < pos[a[i+1]] <= pos[a[i]] + d 是否成立
        if (current_pos < next_pos && next_pos <= current_pos + d) {
            // 计算需要的最少操作次数
            int distance = next_pos - current_pos;

            // Case 1: 交换 current_pos 和 next_pos
            min_operations = min(min_operations, distance);

            // Case 2: 如果 next_pos + d <= n，考虑使 pos[a[i+1]] 超过 pos[a[i]] + d
            if (current_pos + d + 1 <= n) {
                min_operations = min(min_operations, d + 1 - distance);
            }
        } else {
            min_operations = 0;
        }
    }

    cout << min_operations << endl;
    return 0;
}

时间复杂度为 O(m)