怎么会有如此厚颜无耻的手机
题解
直接膜你
对于每次要打开的应用程序比如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);
}