Criska

归并排序（逆序对）

• 分类: 逆序对, 归并排序 • 标签: 归并排序, 逆序对

【模板】逆序对

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
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=50000;
int n,a[N],cnt,c[N];
inline int sortt(int l,int r)
{
	if(l>=r) return 0;
	if(l+1==r)
	{
		if(a[l]>a[r])
		{
			swap(a[l],a[r]);
			cnt++;
		}
		return 0;
	}
	int m=(l+r)/2;
	sortt(l,m);sortt(m+1,r);
	int x=l,y=m+1,t=l;
	while(x<=m&&y<=r)
	{
		if(a[x]<=a[y]) c[t++]=a[x++];
		else
		{
			c[t++]=a[y++];
			cnt+=m-x+1;
		}
	}
	if(x<=m)
		for(int i=x;i<=m;++i)
			c[t++]=a[i];
	if(y<=r)
		for(int i=y;i<=r;++i)
			c[t++]=a[i];
	for(int i=l;i<=r;++i)
		a[i]=c[i];
	
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	sortt(1,n);
	printf("%d",cnt);
	return 0;
}

【例题】火柴排队

  • 这道题好有意思……刚开始根本没想到是用逆序对来做的

  • 首先要记录下来a和b数组中每一个数的大小位置，然后再开一个数组，记录一个数组对应另一个数组的大小相同的数的位置，比如：

    a:1 3 4 2
    b:1 7 2 4

  • 就可以转化为：

    a:1 3 4 2
    b:1 4 2 3

  • 接下来再开一个c数组，记录a对应b的相对位置：

    c:1 4 2 3

  • 对于a中数组的顺序，1在b中的位置是1,3在b中的位置是4,4在b中的位置是2,2在b中的位置是3

  • 答案就是c的逆序对的个数。
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200000;
const int p=99999997;
int a[N],n,b[N],tmp[N],c[N];
long long cnt=0;
struct node{
	long long b;
	int w;
}e[N];
struct node2{
	long long b;
	int w;
}t[N];
inline int cmp(const node & x,const node & y)
{
	return x.b<y.b;
}
inline int cmp2(const node2 & x,const node2 & y)
{
	return x.b<y.b;
}
inline int sortt(int l,int r)
{
	if(l>=r) return 0;
	if(l+1==r)
	{
		if(c[l]>c[r])
		{
			cnt=(cnt+1)%p;
			swap(c[l],c[r]);
		}
		return 0;
	}
	int m=(l+r)/2;
	sortt(l,m);sortt(m+1,r);
	int x=l,y=m+1,t=l;
	while(x<=m&&y<=r)
	{
		if(c[x]<=c[y]) tmp[t++]=c[x++];
		else
		{
			tmp[t++]=c[y++];
			cnt=(cnt+m-x+1)%p;
		}
	}
	if(x<=m)
		for(int i=x;i<=m;++i)
			tmp[t++]=c[i];
	if(y<=r)
		for(int i=y;i<=r;++i)
			tmp[t++]=c[i];
	for(int i=l;i<=r;++i)
		c[i]=tmp[i];
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		long long a1;
		scanf("%lld",&a1);
		e[i].b=a1;
		e[i].w=i;
	}
	for(int i=1;i<=n;++i)
	{
		long long a1;
		scanf("%lld",&a1);
		t[i].b=a1;
		t[i].w=i;
	}
	sort(e+1,e+n+1,cmp);
	sort(t+1,t+n+1,cmp2);
	for(int i=1;i<=n;++i)
	{
		a[e[i].w]=i;
		b[t[i].w]=i;
		//c[i]=t[a[e[i].w]].w;
	}
	for(int i=1;i<=n;++i)
	{
		c[i]=t[a[i]].w;
	}
	sortt(1,n);
	printf("%lld",cnt);
	return 0;
}