题目传送门

:::warning[注意] 更新：请开快读。

感谢 kobelukuankuan 提出。 :::

前言

考完 CSP 意外看了看这道题，发现自己的暴力与别的题解相比显得格格不入，算了算时间复杂度，感觉有点悬，于是本题解也提供暴力做法。

于是本题解更新了。感谢 jiang_yitao 的指出。

解析

题目大意

有一些奶牛，这些奶牛有原先的排列，每只奶牛可以向左移动若干个单位，想要将它们变成最终的排列，求最少移动步数。

考察知识

本题考查排序和模拟（或者说带了贪心算法）。

暴力思路

输入，然后判断这奶牛是否已经满足最终想要的排序，（其实不加这个特判也可以），接着我们从左到右枚举每一头牛，如果遇到与目标的不相符，则去循环找它应该在的位置（即在目标中的位置），接着将其移动（本处我是暴力方法，就是临时存储一下，然后统一往后移，最前面的那一个改为一开始临时存储的最后面的那一个数据），次数加一，然后判断的牛的编号的指针加一，下移至下一头牛，继续执行直到超过总牛数。

优化思路

模拟一下样例。

我们设 $pos[i]$ 表示数 $i$ 在对照组 $b$ 中的位置。

则我们得到了下面的结果。

a:5 1 3 2 4
b:4 5 2 1 3
p:4 3 5 1 2

此时，我们同样把 $a$ 数组替换为 $p$，即 $a[i]$ 现在表示为其在数组 $b$ 中的位置。

原a:5 1 3 2 4
b:4 5 2 1 3
p:4 3 5 1 2
现a:2 4 5 3 1

这时候我们就会发现：那些需要移动的奶牛，即现在的 $a$ 数组中破坏单调上升的那些元素。我们统计有多少个这样的元素即可。

代码

以下是暴力的代码。注意：此代码由于洛谷评测机等差异导致先前能通过，现在却无法通过。以下代码只能在 hydro 通过。请开快读。

:::error[先前的代码]

#include<bits/stdc++.h>
using namespace std;
const int N=0x9fffff;
int n,k,a[N],b[N],ls[N],now=1,sum=0,ls1;//ls1是在B数组中A数组想要的数的位置 
string s;
int same()
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			return 0;
		}
	}
	return 1;
}

void move(int num,int from,int to)
{
	int ls2=num;
	for(int i=from-1;i>=to;i--)
	{
		a[i+1]=a[i];
	}
	a[to]=ls2;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		cin>>b[i];
	}
	if(same()==true)
	{
		cout<<0;
		return 0;
	}
	while(now<=n)
	{
		if(a[now]!=b[now])
		{
			for(int i=now+1;i<=n;i++)
			{
				if(a[i]==b[now])
				{
					ls1=i;
					break;
				}
			}
			move(a[ls1],ls1,now);
			sum++;
		}
		now++;
	}
	cout<<sum;
}

:::

以下是最后能通过的代码。

#include<bits/stdc++.h>
using namespace std;
const int N=0x9fffff;
int n,k,a[N],b[N],ls[N],now=1,sum=0,ls1;//ls1是在B数组中A数组想要的数的位置 
string s;
inline int read()
{
    int k=0,f=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9')
    {
        if(c=='-')
		{
			f=-1;
		}
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9')
	{
		k=k*10+c-'0';
		c=getchar_unlocked();
	}
    return k*f;
}

inline int same()
{
	for(int i=1;i<=n;i++)
	{
		if(a[i]!=b[i])
		{
			return 0;
		}
	}
	return 1;
}

inline void move(int num,int from,int to)
{
	int ls2=num;
	for(register int i=from-1;i>=to;i--)
	{
		a[i+1]=a[i];
	}
	a[to]=ls2;
}

int main()
{
	n=read();
	for(register int i=1;i<=n;i++)
	{
		a[i]=read();
	}
	for(register int i=1;i<=n;i++)
	{
		b[i]=read();
	}
	if(same()==true)
	{
		printf("0");
		return 0;
	}
	while(now<=n)
	{
		if(a[now]!=b[now])
		{
			for(int i=now+1;i<=n;i++)
			{
				if(a[i]==b[now])
				{
					ls1=i;
					break;
				}
			}
			move(a[ls1],ls1,now);
			sum++;
		}
		now++;
	}
	printf("%d",sum);
}