题目描述
有两个长度为 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$. 有思路了代码就简单了 代码如下
1 |
|