CSL的魔法(并查集) “新智认知” 杯上海高校程序设计竞赛暨第十七届上海大学程序设计春季联赛

题目描述

有两个长度为 n 的序列，$a0,a_1,…,a{n-1}$和$b0,b_1,…,b{n-1}$。CSL 有一种魔法，每执行一次魔法，可以任意挑选一个序列并任意交换序列中两个元素的位置。CSL 使用若干次魔法，得到最终的序列 a 和 b，并且想要让 的值最小化。求解 CSL 至少使用多少次魔法，能够达到最小化的目标。

输入描述:

第一行有一个整数 n，表示序列的长度。 接下来两行，每行有 n 个整数，分别表示初始序列 a 和 b。 输入数据保证每个序列里的数两两不同。 $2<=n<=10^5$ $2<=a_i,b_i<=10^5$

输出描述:

在一行输出一个整数，表示最少使用的魔法次数。

示例1

输入

2 1 2 1 2

输出

1

示例2

输入

2 1 2 2 1

输出

0

---

$PS$.$x->y$表示$a[x]$当前应该对应的数字为$b[y]$ 首先要知道 - 最终结果一定是$a[i]$升序排列,$b[i]$降序排列或者反过来,这样保证$sum{a[i]b[i]}$的结果最小 在一个$a,b$数组对中一定都为$x->y$,$y->z$,$z->x$这类情况.或者是$x->y$,$y->z$,$z->q$,$q->$x等等,这里我们称这类现象为环,定义环的大小为环中数字个数(第一种大小为3,第二种为4).极端情况下环的大小为$n$.且数组中的数都在某一环内(因为每个数都能对应另外一个数) 这里不难推断出一个大小为$x$的环需要$x-1$次操作才能让两个数字对应起来.(比如$x->y$,$y->z$,$z->x$,需要交换其中某两个数才能使得$x->x$,$y->y$,$z->z$). 所以这道题就转化为了求环的个数 所以离散化+*并查集就能解决了 这里用离散化主要是因为数据类型为$[1,1e9]$,而$n$大小只有$1e5$. 有思路了代码就简单了 代码如下

#include <map>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define mid(a, b) ((a + b) / 2)
#define OUT freopen("out.txt", "w", stdout)
#define mem(a, b) memset(a, b, sizeof(a))
#define DEBUG(a) cout << (a) << endl
#define IN freopen("in.txt", "r", stdin)
#define IO                       
    ios::sync_with_stdio(false); 
    cin.tie(0);                  
    cout.tie(0);
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
const int PI = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
typedef pair<int,int> PIR;
int a[maxn];
int b[maxn];
struct node
{
    int a, b;
} t[maxn];
void disc(int n)    //离散化
{
    sort(b, b + n);
    int m;
    m = unique(b, b + n) - b;
    for (int i = 0; i < n; ++i)
        a[i] = lower_bound(b, b + m, a[i]) - b + 1;
}
int c[maxn];
int d[maxn];
int disc1(int n)
{
    sort(c, c + n);
    int m;
    m = unique(c, c + n) - c;
    for (int i = 0; i < n; ++i)
        d[i] = lower_bound(c, c + m, d[i]) - c + 1;
    return m;
}

vector<PIR> g;
int pre[maxn];
void init(int n){
    for(int i=0;i<=n;i++){
        pre[i] = i;

    }
}
/*并查集*/
int _find(int x){
    if(x != pre[x])
        pre[x] = _find(pre[x]);
    return pre[x];
}
void combine(int x,int y){
    int fx = _find(x);
    int fy = _find(y);
    if(x>y)
        swap(x,y);
    if(fx!=fy)
        pre[fx] = fy;
}
/******/
int vis[maxn];
bool vv[maxn];
void dfs(int i){ //将数组分割成不同的环
    if(!vv[vis[i]]){
        vv[vis[i]] = true;
        combine(vis[i],i);
        dfs(vis[i]);
    }
}

int main()
{

    int n;
    cin >> n;
    init(n+5);
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        a[i] = b[i];
    }
    for(int i=0;i<n;i++){
        cin >> c[i];
        d[i] = c[i];
    }
    int buf = disc1(n);
    disc(n);
    for (int i = 0; i < n; i++)
    {
        d[i] = buf - d[i] + 1;  
        g.push_back({a[i], d[i]});//a[i]==d[i]表示这两个数相互对应,已经归位了
    }
    int cn3;
    cn3 = 0;
    for(PIR i:g)
        vis[i.second] = i.first;    //
    for(PIR i:g)
        dfs(i.second);
    mem(vv,0);
    for(PIR i:g){
        int pos = _find(i.second);
        if(!vv[pos]){   //如果遇到新的环,cnt++
            cn3++;
            vv[pos] = true;
        }
    }
    DEBUG(g.size()-cn3); //最终结果就为n-环的个数
    return 0;
}