提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

CoderForces 518C Anya and Smartphone (模拟)

模拟 and
2023-09-11 14:17:19 时间

题意：给定一个手机，然后一共有 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;
}

 

相关文章