给你一个排列，要求你每次操作任选4个数字交换位置，最小需要多少次操作才能变成有序排列。
思路：考虑使用并查集，将i和a[i]所在的集合并。这样合并后的每个集内部元素是可以自由排列形成最终答案的。对于长度为1的集，说明i与a[i]在一个位置上，不需要操作；对于长度为2的集，两个可以组成一对进行操作；对于长度为3的集，需要用一个辅助元素与之组合；对于长度为4的集，肯定是选择它自己了；对于长度大于4的集，我们任选其中4个元素，只能使3个定序，另一个必定还是不对位的，因此操作次数是集的大小/3，此外集的大小%3还要讨论一下。
有位佬跟我说可以用基环树，但我还没有学过。等我学了，我再更新这篇blog……
代码：
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
| #ifndef VLSMB_VS
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip>
#include <set>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <cstdio>
#include <cmath>
#endif
#define int long long
#define pii pair<int,int>
#define endl '\n'
#define veci vector<int>
#define vecpi vector<pii >
#define mpi map<int,int>
#define mpc map<char,int>
#define inf 0x7fffffffffffffff
#define eps 1e-8
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define seti set<int>
#define mulseti multiset<int>
#define setpi set<pii >
#define priqli priority_queue<int,veci,less<int> >
#define priqgi priority_queue<int,veci,greater<int> >
#define priqgpi priority_queue<pii,vecpi,greater<pii > >
using namespace std;
const int N = 1000000;
void solve();
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t=1;
cin>>t;
while(t--)solve();
cout.flush();
return 0;
}
int getpar(veci&d,int x)
{
if(x==d[x])return x;
d[x]=getpar(d,d[x]);
return d[x];
}
void merg(veci&d,int x,int y)
{
x=getpar(d,x);
y=getpar(d,y);
if(x==y)return;
d[x]=y;
}
void solve()
{
int n;
cin>>n;
veci d(n+1);
for(int i=1;i<=n;i++)d[i]=i;
mpi h;
int x;
for(int i=1;i<=n;i++)
{
cin>>x;
merg(d,x,i);
}
for(int i=1;i<=n;i++)h[getpar(d,i)]++;
int ans=0;
int res=0;
for(const auto&p:h)
{
if(p.second==4)ans++;
else if(p.second>4)
{
ans+=p.second/3;
if(p.second%3==2)res++;
}
else if(p.second==2)res++;
else if(p.second==3)ans++;
}
cout<<ans+res/2+res%2<<endl;
}
|
