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

题目描述

有两个长度为 n 的序列,$a0,a_1,…,a{n-1}$和$b0,b_1,…,b{n-1}$。CSL 有一种魔法,每执行一次魔法,可以任意挑选一个序列并任意交换序列中两个元素的位置。CSL 使用若干次魔法,得到最终的序列 ab,并且想要让 的值最小化。求解 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#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;
}

觉得文章不错的话可以请我喝一杯茶哟~
  • 本文作者: bestsort
  • 本文链接: https://bestsort.cn/2019/04/27/371/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-SA 许可协议。转载请注明出处!并保留本声明。感谢您的阅读和支持!
-------------本文结束感谢您的阅读-------------