【IOI2015】sorting

Source

IOI2015
bzoj4371
uoj233

Hint

请先思考后再展开

考虑有n个带编号的盘子和n个带编号的苹果,然后A交换盘子,B交换苹果
这样就能把两个人拆开来了

Solution

请先思考后再展开

首先这东西可以二分,因为如果有序后,B可以每次做A的逆操作
然后考虑置换的环数量,显然步数为n-环数
然后输出方案的话,考虑值形成的环,按这个去推一下即可
时间复杂度 $O(nlogn)$

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
typedef long long ll;
ll qread()
{
ll ans=0;char c=getchar();
while(c<'0' or c>'9') c=getchar();
while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
return ans;
}
#define pr pair<int,int>
#define FR first
#define SE second
#define MP make_pair
#define PB push_back
const int MAX_N=6e5+10;
int n,m,a[MAX_N],b[MAX_N],fx[MAX_N],fy[MAX_N];
int now[MAX_N],to[MAX_N];
bool v[MAX_N];
bool check(int mid)
{
memcpy(b,a,sizeof a);for(int i=1;i<=mid;i++) swap(b[fx[i]],b[fy[i]]);
for(int i=1;i<=n;i++) now[b[i]]=i;
// for(int i=1;i<=n;i++) to[i]=now[i];
memset(v,0,sizeof v);int cnt=0;
for(int i=1;i<=n;i++) if(!v[i])
{
int x=i;v[x]=1;cnt++;
while(now[x]!=i) x=now[x],v[x]=1;
}
return n-cnt<=mid;
}
int ans;vector<pr> end;
void solve()
{
int l=0,r=m;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
memcpy(b,a,sizeof a);for(int i=1;i<=ans;i++) swap(b[fx[i]],b[fy[i]]);
// for(int i=1;i<=n;i++) to[i]=b[i];
// printf("%d\n",ans);
for(int i=1;i<=n;i++) now[a[i]]=i;
int tmp=0;memset(v,0,sizeof v);
for(int i=1;i<=n;i++) if(!v[i])
{
int x=i;v[x]=1;
while(b[x]!=i)
{
tmp++;swap(a[fx[tmp]],a[fy[tmp]]);swap(now[a[fx[tmp]]],now[a[fy[tmp]]]);
// printf("%d %d\n",now[x]-1,now[b[x]]-1);
end.PB(MP(now[x]-1,now[b[x]]-1));
swap(a[now[x]],a[now[b[x]]]);swap(now[x],now[b[x]]);x=b[x];v[x]=1;
}
}
// while(tmp!=ans) tmp++,puts("0 0");
while(tmp!=ans) tmp++,end.PB(MP(0,0));
}
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
{
n=N;for(int i=1;i<=n;i++) a[i]=S[i-1]+1;
m=M;for(int i=1;i<=m;i++) fx[i]=X[i-1]+1,fy[i]=Y[i-1]+1;
solve();
for(int t=0;t<(int)end.size();t++) P[t]=end[t].FR,Q[t]=end[t].SE;
return ans;
}
// int main()
// {
// // freopen("1.in","r",stdin);
//
// n=qread();for(int i=1;i<=n;i++) a[i]=qread()+1;
// m=qread();for(int i=1;i<=m;i++) fx[i]=qread()+1,fy[i]=qread()+1;
// solve();
// }

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/8565.html
转载请注明出处,谢谢!