E、CSL 的魔法 【模拟】 （“新智认知”杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛）

 1 #include <bits/stdc++.h>
 2 #define INF 0x3f3f3f3f
 3 #define LL long long
 4 #define inc(i, j, k) for(int i = j; i <= k; i++)
 5 #define rep(i, j, k) for(int i = j; i < k; i++)
 6 #define mem(i, j) memset(i, j, sizeof(i))
 7 #define gcd(i, j) __gcd(i, j)
 8 using namespace std;
 9 const int MAXN = 2e5+10;
10 map<int, int>ida, idb, xa, xb;
11 int a[MAXN], b[MAXN], tpa[MAXN], tpb[MAXN];
12 
13 bool cmp(int a, int b)
14 {
15     return a > b;
16 }
17 int N;
18 
19 int main()
20 {
21     scanf("%d", &N);
22     inc(i, 1, N){ scanf("%d", &a[i]); tpa[i] = a[i]; xa[a[i]] = i;}
23     inc(i, 1, N){ scanf("%d", &b[i]); tpb[i] = b[i]; xb[b[i]] = i;}
24     sort(tpa+1, tpa+1+N);
25     inc(i, 1, N) ida[tpa[i]] = i;
26     sort(tpb+1, tpb+1+N, cmp);
27     inc(i, 1, N) idb[tpb[i]] = i;
28     int ans = 0;
29     inc(i, 1, N)
30     {
31         if(ida[a[i]] != idb[b[i]]){
32             ans++;
33             int nxtb = tpb[ida[a[i]]];
34             int nxt = xb[nxtb];
35             xb[b[i]] = nxt;
36             xb[b[nxt]] = i;
37             swap(b[i], b[nxt]);
38         }
39     }
40 
41     printf("%d\n", ans);
42     return 0;
43 }