竞赛讨论区 > CSL 的魔法
头像
我不会玩锐雯
编辑于 2019-03-31 17:18
+ 关注

CSL 的魔法

/*弱鸡萌新第一次写,写的不好不要喷啊,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) 回帖
加载中...
话题 回帖