首页 > 代码库 > CodeForces 518C - Watto and Mechanism(模拟)
CodeForces 518C - Watto and Mechanism(模拟)
题意:有n(1 <= n <= 10^5)个应用,每屏有k(1 <= k <= 10^5)个应用,现在有m(1 <= m <= 10^5)个操作,每次操作会使用一个应用(使用时需滑到应用所在的屏),使用后此应用与前边的相邻应用交换位置,退出此应用后会回到初始屏。问这m次操作总的滚动屏幕次数。
模拟即可。
#include<cstdio> #include<cstring> #include<cctype> #include<cstdlib> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<deque> #include<queue> #include<stack> #include<list> typedef long long ll; typedef unsigned long long llu; const int MAXN = 100 + 10; const int MAXT = 100000 + 10; const int INF = 0x7f7f7f7f; const double pi = acos(-1.0); const double EPS = 1e-6; using namespace std; int n, m, k, a[MAXT], loc[MAXT][2]; vector<int> g[MAXT]; int main(){ memset(loc, -1, sizeof loc); scanf("%d%d%d", &n, &m, &k); for(int i = 0; i < n; ++i) scanf("%d", a + i); int lur = 0; for(int i = 0; i < n; ++i){ int j; for(j = 0; j < k && i + j < n; ++j){ g[lur].push_back(a[i + j]); loc[a[i + j]][0] = lur; loc[a[i + j]][1] = j; } ++lur; i = i + j - 1; } llu ans = 0; while(m--){ scanf("%d", &lur); ans += (llu)(loc[lur][0] + 1); if(loc[lur][1] == 0){ if(loc[lur][0]){ int ll = loc[lur][0]; int tmp = g[ll - 1][k - 1]; loc[lur][0] = ll - 1; loc[lur][1] = k - 1; loc[tmp][0] = ll; loc[tmp][1] = 0; swap(g[ll - 1][k - 1], g[ll][0]); } } else{ int r1 = loc[lur][0]; int r2 = loc[lur][1]; int tmp = g[r1][r2 - 1]; loc[lur][1] = r2 - 1; loc[tmp][1] = r2; swap(g[r1][r2 - 1], g[r1][r2]); } } printf("%I64u\n", ans); return 0; }
CodeForces 518C - Watto and Mechanism(模拟)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。