CSU 2130~湖南多校对抗第八场 C

2130: Permutations

Submit Page   Summary   Time Limit: 1 Sec     Memory Limit: 128 Mb     Submitted: 79     Solved: 33

---

Description

给定两个1~n的排列A, B。每次可以把A的最后一个数取出，插入到A的任何一个位置（最前面或者任何两个数中间）。 问最少几次可以把A转化为B。

Input

第一行为一个整数n。 第二行为1~n的一个排列，表示A。 第三行为1~n的一个排列，表示B。

Output

一个整数即最少操作次数。

Sample Input

5

1 5 2 3 4

1 2 3 4 5

Sample Output

3

Hint

30%：n <= 100

50%：n <= 1000

100%: n <= 200000

Source

Author

lfw

#include <cstdio>

const int maxn=2e5+;

int a[maxn];

int b[maxn];

int c[maxn];

int main() {

    int n;

    int flag=;

    scanf("%d",&n);

    for(int i=; i<=n; i++) {

        scanf("%d",&a[i]);

    }

    for(int i=; i<=n; i++) {

        scanf("%d",&b[i]);

        c[b[i]]=i;

    }

    for(int i=; i<=n; i++) {

        if(a[i]==b[i]) continue;

        else {

            flag=;

        }

    }

    if(flag==) {

        printf("0\n");

    } else {

        for(int i=; i<=n; i++) {

            a[i]=c[a[i]];

        }

        for(int i=; i<=n; i++) {

            if(a[i]<a[i-]) {

                printf("%d\n",n-i+);

                break;

            }

        }

    }

    return ;

}