B. The Forbidden Permutation

一定要注意题目中说的是对于all i满足才算不好的,我们做的时候只要破坏一个i这个a就不算好的了,被这一点坑了,没注意到all。

我们只需要从前往后做一遍,对于满足题中不等式的a[i]我们的操作是把a[i + 1]移到a[i]前面,一种操作是,将a[i + 1]向后移直到破坏后面的条件,(注意不能移出边界)
最后两种操作取最小值即可,如果我们未操作时题目中就有不满足的a[i],此时答案就为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int p[N], a[N];

void run()
{
memset(p, 0, sizeof p);
int n, m, d; scanf("%d%d%d", &n, &m, &d);
for(int i = 1; i <= n; ++ i)
{
int x; scanf("%d", &x);
p[x] = i;
}
for(int i = 1; i <= m; ++ i) scanf("%d", &a[i]);
int ans = 1e9;
for(int i = 1; i + 1 <= m; ++ i)
{
if(p[a[i + 1]] < p[a[i]] || p[a[i + 1]] > p[a[i]] + d)
{
cout << 0 << endl;
return;
}
if(p[a[i + 1]] > p[a[i]]) ans = min(ans, p[a[i + 1]] - p[a[i]]);
if(p[a[i + 1]] <= p[a[i]] + d)
if(d + 2 <= n) ans = min(ans, p[a[i]] + d + 1 - p[a[i + 1]]);
}
printf("%d\n", ans);
}

int main()
{
// freopen("1.in", "r", stdin);
int t;cin >> t;
while(t --) run();
return 0;
}