Permutation

NC219808. Permutation

描述

You are given two permutations $a_{}$ and $b_{}$ of length $n_{}$ .
A permutation is a sequence of length $n_{}$ integers from $1_{}$ to $n_{}$ , in which all the numbers occur exactly once. For example, $[1], [1,3,2], [3,1,5,2,4]_{}$ are permutations, and $[2], [1,1]_{}$ are not.

There are two types of operations as follow：

Remove the first integer in $a_{}$ . Then append any integer at the end of $a_{}$ .
Choose an $a_i(1\leq i\leq n)$ and modify it to any integer.

You have to find the minimum number of operations to make $a_{}$ and $b_{}$ the same.
Be attention, you do not have to keep $a_{}$ in a permutation during the process.

输入描述

The first line contains an integer  — the length of  and  .
The second line contains  integers  .
The third line contains  integers  .
It is guaranteed that  and  are both permutations.

输出描述

Output the minimum number of operations to make  and  the same.

示例1

输入:

5
5 2 3 4 1
5 3 2 1 4

输出:

说明:

For the first example, there is a possible way:
1. Remove the first integer in $a_{}$ and append 4, now $a_{}$ becomes $[2,3,4,1,4]_{}$ .
2. modify $a_1$ to $5_{}$ , now $a_{}$ becomes $[5,3,4,1,4]_{}$ .
3. modify $a_3$ to $2_{}$ , now $a_{}$ becomes $[5,3,2,1,4]_{}$ .
So it only takes $3_{}$ operations to convert $a_{}$ into $b_{}$ .

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 682ms, 内存消耗: 6532K, 提交时间: 2021-03-27 15:04:38

#include<iostream>
#include<algorithm>
using namespace std;
int a[1000001],b[1000001];
int main(){
	int n,c;cin>>n;
	for(int i=0;i<n;++i)cin>>c,a[c]=i;
	for(int i=0;i<n;++i){
		cin>>c;
		if(a[c]-i>=0)b[a[c]-i]++;
	}
	int m=n;
	for(int i=0;i<n;++i)m=min(m,n-b[i]); 
		cout<<m<<endl;
	return 0;
}

上一题

下一题

详情