Codeforces Round 848 (Div. 2) B. The Forbidden Permutation（贪心）

The Forbidden Permutation

给你一个长度为 n 的排列 p 、一个由 m 组成的数组 $a_1,a_2,\dots ,a_m(1\le a_i\le n)$和一个整数 d 组成的数组。不同的整数 $a_1,a_2,\dots ,a_m(1\le a_i\le n)$，以及整数 d 。

设 $pos(x)$ 是 $x$ 在排列 $p$ 中的索引。如果出现以下情况，那么数组 $a$ 就不好。

$pos(a_i)<pos(a_{i+1})\le pos(a_i)+d$ 为所有的 $1\le i<m$ .
例如，排列 p=[4,2,1,3,6,5] 和 d=2 ：

a=[2,3,6] 不是一个好数组。a=[2,6,5] 是好数组，因为 $pos(a_1)=2，pos(a_2)=5$ ，所以不满足条件 $pos(a_2)\le pos(a_1)+d$ 。

a=[1,6,3] 是好数组，因为 $pos(a_2)=5，pos(a_3)=4$ ，所以不满足条件 $pos(a_2)<pos(a_3)$ 。

在一步棋中，你可以交换排列组合 p 中相邻的两个元素。要使数组 a 变为好数组所需的最少步数是多少？可以证明总是存在一个移动序列使得数组 a 变为好数组。

排列数组是由 n 个不同的整数组成的数组，这些整数从 1 到 n 按任意顺序排列。例如， [2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列( 2 在数组中出现了两次)， [1,3,4] 也不是一个排列( n=3 ，但数组中有 4 )。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1\le t\le 10^4)$。测试用例说明如下。

每个测试用例的第一行包含三个整数 $n、m$ 和 $d(2\le n\le 10^5、2\le m\le n、1\le d\le n)$、排列长度 $p$ 、数组长度 $a$ 和值 $d$ 。

第二行包含 n 个整数 $p_1,p_2,\dots ,p_n(1\le p_i\le n、p_i\ne p_j为i\ne j)$。

第三行包含 m 个独立整数 $a_1,a_2,\dots ,a_m(1\le a_i\le n，a_i\ne a_j为i\ne j)$。

所有测试用例中 n 的总和不超过 $5\cdot 10^5$ 。

输出

对于每个测试用例，打印使数组 $a$ 变为好数组所需的最小移动次数。

样例 #1

样例输入 #1

5
4 2 2
1 2 3 4
1 3
5 2 4
5 4 3 2 1
5 2
5 3 3
3 4 1 5 2
3 1 2
2 2 1
1 2
2 1
6 2 4
1 2 3 4 5 6
2 5

样例输出 #1

1
3
2
0
2

读题很重要
首先，这道题的条件是：
只要存在任何两个元素，使得满足 $pos(a_1)+d<pos(a_2)$ 或者 $pos(a_1)>pos(a_2)$，那么就可以说这是一个好数组。
并且应理解pos数组的含义，pos数组是p数组的元素的索引，所以我们可以先预处理出来pos数组以便于后面的操作。

可以将情况划分成两种：

• 第一种：这个数组已经是好数组。即满足了pos[a[i+1]] <= pos[a[i]] || pos[a[i+1]] > d + pos[a[i]]，那么直接将答案置为$0$。
• 第二种：这个数组不是一个好数组。那么就需要考虑如何使用最少的步数将其变成好数组。

如何将不好的数组变为好数组 ？

• 第一种做法：可以想办法使得存在 $pos(a_i)>pos(a_{i+1})$，那么最优的办法就是让 $pos(a_{i+1})$ 交换到 $pos(a_i)$ 的前面去，这个方法会花费 $pos(a_{i+1})-pos(a_i)$ 的步数。
• 第二种做法：可以想办法使得存在 $pos(a_{i+1})>d+pos(a_i)$，在这里可以给这个式子变个形： $pos(a_{i+1})-pos(a_i)>d$ 这样就变成了让这两个数的差值大于d，那么就可以让 $pos(a_{i+1})$ 往右移动，然后让 $pos(a_i)$ 往左移动，这样消耗的步数就是 $d-(pos(a_{i+1})-pos(a_i))+1$。但是对于这种情况我们需要判断这两个元素是否能够移动的开，如果两个元素都超出边界了都无法满足条件，这个操作就无法成立。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;

int p[N];
int a[N];
int pos[N];
int n,m,d;

void solve(){
    cin >> n >> m >> d;
    for(int i = 1;i <= n;i++){
        cin >> p[i];
        pos[p[i]] = i; 
    }
    for(int i = 1;i <= m;i++)cin >> a[i];

    int ans = 2e9;

    for(int i = 1;i < m;i++){
        if(pos[a[i+1]] <= pos[a[i]] || pos[a[i+1]] > d + pos[a[i]]){
            ans = 0;        //如果存在任何pos(a1) + d < pos(a2)或者pos(a1) > pos(a2)
            break;          //那么这个数组就已经是一个好数组了
        }

        int dis = pos[a[i+1]] - pos[a[i]];  //第一种情况消耗的步数
        ans = min(ans,dis);

        //判断能否移动得开
        //  pos[a[i]] - 1表示从左边界到pos[a[i]]的距离
        //  n - pos[a[i+1]]表示从有边界到pos[a[i+1]]的距离
        //  d - dis + 1表示使得满足pos(a2) - pos(a1) > d所需要的距离
        //  (需要两者相差的距离 - 两者当前的距离)
        if((pos[a[i]] - 1 + n - pos[a[i+1]]) >= d - dis + 1){
            ans = min(ans,d - dis + 1);
        }
    }   
    cout << ans <<endl;
}

int main(){
    int T;cin >> T;
    while(T--){
        solve();
    }
    return 0;
}