CoderForces 518C Anya and Smartphone (模拟)

题意:给定一个手机,然后一共有 n 个app,告诉你每个屏幕最多放 k 个,现在要你运行 m 个app,每次都从第一个屏幕开始滑动,每运行一个,它就和前一个交换位置,第一个就不换了,现在问你要滑动多少次。

析:这个题,没什么算法,就是模拟呗,不过要注意时间,不能TLE,所以我们就得提前把所有的位置都存下来,让查找的时间变成 O(1),否则就会超时,可以用两个数组,也可以用map,一个存编号,一个存位置,

然后运行完后再交换就行了。

代码如下:

#include <iostream>
#include <cstdio>
#include <map>
#include <cmath> using namespace std;
typedef long long LL;
const int maxn = 1e5 + 5;
map<int, int> mp;
map<int, int> mps;
int main(){
int n, m, k, x;
while(scanf("%d %d %d", &n, &m, &k) == 3){
for(int i = 0; i < n; ++i){
scanf("%d", &x);
mp[x] = i+1;
mps[i+1] = x;
} LL ans = 0;
for(int i = 0; i < m; ++i){
scanf("%d", &x);
int t = mp[x];
ans += (LL)ceil((double)t/k);
if(t == 1) continue;
swap(mp[mps[t]], mp[mps[t-1]]);
swap(mps[t], mps[t-1]);
}
printf("%lld\n", ans);
}
return 0;
}
上一篇:【剑指offer】判断一个序列是否是二叉搜索树的后序遍历,C++实现


下一篇:MYSQL数据库相关知识合集