AcWing.5151.程序调用
有 \(n\) 个程序，编号 \(1∼n\)。
初始时，这 \(n\) 个程序都在一个调用队列当中，位于队列第 \(i\) 位的是编号为 \(a_i\) 的程序。
每个程序都有一个调用级别，根据程序在队列中的排位，排在第 \(1∼k\) 位的程序属于 \(1\) 级程序，排在第 \(k+1∼2k\) 位的程序属于 \(2\) 级程序，以此类推。
每 \(1\) 级只包含 \(k\) 个程序，最后 \(1\) 级可能不到 \(k\) 个程序。
现在，我们要依次进行 \(m\) 次程序调用，每次调用这 \(n\) 个程序之一。
其中，第 \(i\) 次调用的是编号为 \(b_i\) 的程序。
关于程序调用，有以下相关信息：
- 一个程序有可能被多次调用。
- 一个程序被调用一次所需付出的成本等于其被调用时的级别。
- 一个程序被调用一次后，其在队列中的位置会前进一位，也就是说，该程序会与队列中前一位的程序互换位置。注意，如果程序本来就排在第一位，则不会改变位置。程序的位置变动可能会导致程序的调用级别发生变动。
请你计算，这 \(m\) 次程序调用所需花费的总成本。
输入格式
第一行包含三个整数 \(n,m,k\)。
第二行包含 \(n\) 个整数 \(a_1,a_2,…,a_n\)，保证 \(a_1∼a_n\) 是一个 \(1∼n\) 的排列。
第三行包含 \(m\) 个整数 \(b_1,b_2,…,b_m\)。
输出格式
一个整数，表示 \(m\) 次程序调用所需花费的总成本。
数据范围
前 33 个测试点满足 \(1≤n,m,k≤10\)。
所有测试点满足 \(1≤n,m,k≤10^5，1≤a_i,b_i≤n\)，保证 \(a_i∼a_n\) 是一个 \(1∼n\) 的排列。
输入样例1：
8 3 3
1 2 3 4 5 6 7 8
7 8 1
输出样例1：
7
输入样例2：
5 4 2
3 1 5 2 4
4 4 4 4
输出样例2：
8
思路分析：模拟哈希数组：定义一个数组a[N],用来存放输入的输入程序；另一个数组b[N]，用来存放输入程序的下标；依次读入，依次构
建哈希映射。进行m次操作，每次读入一个数x，获取它的下标b[x]，算出它的调度级别。让t=b[x]，y=a[t-1]，即t是x的下标，y是x的前
一个数，交换数值：a[t]和a[t-1]交换，交换下标：b[x]和b[y]交换，如果下标为1就不需要交换，直到程序结束。输出答案。
值得注意的是，如果k为1，一级一个调度，n=10^5,m=10^5,每次只对最后一个程序进行调度，答案会爆int。
代码：
#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=100010;
int a[N],b[N];
int n,m,k,x;
ll res;
int main(){
cin>>n>>m>>k;
for(int i = 1;i <= n;i++) cin>>a[i],b[a[i]]=i;
while(m--){
cin>>x;
int t=b[x];
res += ceil(t*1.0/k);
if(b[x] != 1){
int y = a[t-1];
swap(a[t],a[t-1]);
swap(b[x],b[y]);
}
}
cout<<res;
return 0;
}