怎么会有如此厚颜无耻的手机题解直接膜你对于每次要打开的应用程序比如B站，暴力搜一遍找到它的位置，然后直接按题意膜你即可。可以发现每次操作的最坏复杂度就是搜一遍的O(n)，而总共有m个操作，复杂度总共为O(nm)，所以对于10^{5}的数据来说会超时。于是我们想到了直接映射即可，用一个数组 id[i] 记录编号为i的应用程序的位置（注意这里不是第几个屏幕）对于每一个操作，要打开编号为b的应用程序，有以下步骤：定义 pos=id[b] ，表示该应用程序的编号 res+=(pos-1)/k+1 ， (pos-1)/k) 就是求滑到该应用程序所在屏幕所需的步数，然后 +1 就表示打开这个应用程序开始颓废。 --id[a[pos]] ++id[a[pos-1]] 。 a[pos] 表示这个应用程序的编号(注意不能直接用 b ，然后 -- 就表示往前调。第二步往后调也是同样的原理。注意应用程序在第一个的话就不要调了。然后交换 a[pos] 和 a[pos-1] 的值即可，其实就是交换它和它前面的应用程序的编号。我用的是位运算交换，其实和朴素交换方法的没什么两样。最后输出结果 res 即可。注意 res 要开long\ long，因为 imath ^{2}$比MAX\_INT要大代码 #include<stdio.h> int n,m,k,a[100010],id[100010],b,pos,temp; long long res; //注意long long int main() { scanf("%d%d%d",&n,&m,&k); for(register int i=1;i<=n;++i) { scanf("%d",&a[i]); id[a[i]]=i; //记录编号对应的位置 } while(m--) { scanf("%d",&b); pos=id[b]; //获取pos res+=(pos-1)/k+1; //更新答案res if(pos==1) continue; //如果应用程序在第一个就不用调了 --id[a[pos]]; //交换他们的编号对应的位置映射 ++id[a[pos-1]]; a[pos]^=a[pos-1]; //位运算交换应用程序的编号，其实和朴素交换方法的没什么两样。 a[pos-1]^=a[pos]; a[pos]^=a[pos-1]; } printf("%lld\n",res); }

洛谷CF518C题解

damage

~~怎么会有如此厚颜无耻的手机~~

题解

直接膜你

对于每次要打开的应用程序~~比如B站~~，暴力搜一遍找到它的位置，然后直接按题意膜你即可。

可以发现每次操作的最坏复杂度就是搜一遍的O(n)，而总共有m个操作，复杂度总共为O(nm)，所以对于10^{5}的数据来说会超时。

于是我们想到了直接映射即可，用一个数组id[i]记录编号为i的应用程序的位置（注意这里不是第几个屏幕）

对于每一个操作，要打开编号为b的应用程序，有以下步骤：

定义pos=id[b]，表示该应用程序的编号
res+=(pos-1)/k+1，(pos-1)/k)就是求滑到该应用程序所在屏幕所需的步数，然后+1就表示打开这个应用程序~~开始颓废~~。
--id[a[pos]] ++id[a[pos-1]]。a[pos]表示这个应用程序的编号(注意不能直接用b，然后--就表示往前调。第二步往后调也是同样的原理。注意应用程序在第一个的话就不要调了。
然后交换a[pos]和a[pos-1]的值即可，其实就是交换它和它前面的应用程序的编号。我用的是位运算交换，其实和朴素交换方法的没什么两样。

最后输出结果res即可。

注意`res`要开long\ long，因为[链接登录后可见]^{2}$比MAX\_INT要大

代码

#include<stdio.h>
int n,m,k,a[100010],id[100010],b,pos,temp;
long long res; //注意long long
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		id[a[i]]=i; //记录编号对应的位置
	}
	while(m--)
	{
		scanf("%d",&b);
		pos=id[b]; //获取pos
		res+=(pos-1)/k+1; //更新答案res
		if(pos==1) continue; //如果应用程序在第一个就不用调了
		--id[a[pos]]; //交换他们的编号对应的位置映射
		++id[a[pos-1]];
		a[pos]^=a[pos-1]; //位运算交换应用程序的编号，其实和朴素交换方法的没什么两样。
		a[pos-1]^=a[pos];
		a[pos]^=a[pos-1];
	}
	printf("%lld\n",res);
}