/*弱鸡萌新第一次写,写的不好不要喷啊,TAT; 一:首先最终的结果肯定是a数组最小的配对b数组最大的, a数组第二小的配对b数组第二大的,以此类推。。。。。。 所以我们对两个数组分别按升序和降序排列即可得到结果的数组。 二:以1 2 3为例 b a c 先得到初始图 1-b,2-a,3-c; 结果数组为1 2 3 c b a 把新的边加进去 1-c-3-a-2-b-1, 形成一个环,对于每个环交换的次数即对答案的贡献是环中元素个素/2-1; 图的意义:结果中1要和c配对,但是原式中c是和3配对的, 不是1就往下走,结果中3要和a配对,但是原式中a是和2配对的, 不是1继续往下走,结果中2要和b配对,原式中b和1配对,找到一个环。 对于整张图有多个环,对每个环的贡献求和即可。 #include <map> #include <set> #include <ctime> #include <stack> #include <cmath> #include <queue> #include <bitset> #include <string> #include <vector> #include <cstdio> #include <cctype> #include <fstream> #include <cstdlib> #include <sstream> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define LL long long ///int a[12]= {0,31,59,90,120,151,181,212,243,273,304,334}; const int INF = 0x3f3f3f3f; ///1 061 109 567 const int negative_infinite = 0xcfcfcfcf; ///-808 464 433 const int mod = 1e9 + 7; const int MAXN = 100007; int a[MAXN], b[MAXN], c[MAXN], d[MAXN]; bool fc[MAXN]; bool fd[MAXN]; int n; int ans = 0; map<int, int> mc; map<int, int> mb; void dfs(int idex) { int flag = c[idex]; fc[idex] = true; int x = d[idex]; int id = mb[x]; fd[id] = true; int cnt = 1; while(a[id] != flag) { idex = mc[a[id]]; fc[idex] = true; x = d[idex]; id = mb[x]; fd[id] = true; cnt++; } //printf("cnt = %d\n", cnt); ans += cnt - 1; } int main() { scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); c[i] = a[i]; } for(int i = 0; i < n; i++) { scanf("%d", &b[i]); mb[b[i]] = i; d[i] = b[i]; } sort(c, c + n, less<int>()); for(int i = 0; i < n; i++) mc[c[i]] = i; sort(d, d + n, greater<int>()); for(int i = 0; i < n; i++) { if(!fc[i]) { dfs(i); } } printf("%d\n", ans); return 0; }
全部评论
(0) 回帖