每日打卡-16

leapssisbird / 2023-05-04 / 原文

一.问题描述

农夫约翰有 N头奶牛，编号 1∼N。

约翰让它们排成一排，以便拍照。

最初，奶牛从左到右按照 a1,a2,…,aN 的顺序排列。

但是，约翰希望奶牛从左到右按照 b1,b2,…,bN 的顺序排列。

为此，他需要对队列进行一系列的调整操作。

每次操作可以选择任意一头奶牛并将其向左移动一些位置。

请问，至少需要多少次操作，才能使奶牛按照约翰满意的顺序排列。

二.设计思路

1.i 指针指向 a[0] , j 指针指向b[0],
2.以b数组作为模板，只要 a[i]!=b[j] 我们就一定可以在a数组找到一个相等的数并把它移动到a数组的最前面 ( j 指针并不是与当前i指针指向的数相等，所以 i指针指向不变 )
3.标记一下这个找到的数b[j]，防止重复找.
4.在b数组上的数一定可以在a数组上找到，不论 a[i] 是否等于 b[j] 都将 j指针指向下一个 j++
5.如果 a[i]==b[j] 继续往后移，i指针与j指针指向的数相等， i++

三.流程图

四.伪代码

五.代码实现

#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N],b[N];
bool v[N];  //
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<n;i++)cin>>b[i];
    int ans=0;
    for(int i=0,j=0;i<n&&j<n;j++){
        while(v[a[i]])i++;  //找到第一个没有别标记的数
        if(a[i]!=b[j]){  //总能在a上找到与 b[j] 相等的数
            ans++;
            v[b[j]]=true;
        }else {
            i++;
        }
    }
    cout<<ans;
    return 0;
}