这题是看树状数组是看到的,博客作者说这个可以用归并排序,于是就写了下,发现还好。
对于数组a,归并排序时的合并阶段,分成两段,也就是(start,mid)和(mid,end)(我这里第一段的下标是从start到mid-1,
第二段的下标是从mid到end-1)。用三个下标分别指向前面一段(i),后面一段(j),和新数组下标(idx).那么当出现
num[j] < num[i]的时候,结果就应该加前面一段还没有进入新数组的数据的长度,比如说当前i = 3;j = 8;mid = 5且
num[8] < num[3];那么结果应该加上(5-3=2)(记住我的前面一段是到mid-1结束),因为在这次归并的过程中要移动(5-3=2)次,
因为(num[3],num[8])是一个逆序对,同时(num[4],num[8])是一个逆序对(似乎这里理解起来有点困难-_-,可以画一个图,
自己手动执行下,比如第一个样例就行(9,1,0,5,4),自己手动执行下,就知道为什么了)。那么这样的话应该就好做了,
最后一点就是结果会超int用long long或者__int64存
代码如下(依旧,建议读者先自己写)

CODE
1
/**//*
2
ID:Klion
3
PROG:POJ_2299
4
LANG:C++
5
*/
6
#include<iostream>
7
using namespace std;
8
int num[500006];
9
__int64 total;
10
void merge(int start,int mid,int end)
11

{
12
int tmp[500006];
13
int i = start;
14
int j = mid;
15
int idx = 0;
16
//放到tmp数组里面
17
for(;i < mid && j < end;)
18
{
19
if(num[i] < num[j])
20
{
21
tmp[idx] = num[i];
22
idx++;
23
i++;
24
}
25
else
26
{
27
tmp[idx] = num[j];
28
idx++;
29
j++;
30
total += (mid-i);
31
}
32
}
33
//把剩下的都放到tmp数组里面去
34
for(;i < mid;i++)
35
{
36
tmp[idx++] = num[i];
37
}
38
for(;j < end;j++)
39
{
40
tmp[idx++] = num[j];
41
}
42
//把排好序的再赋值到num数组中
43
for(j = start,i = 0;i < idx;i++,j++)
44
num[j] = tmp[i];
45
}
46
void merge_sort(int start,int end)
47

{
48
if(start + 1 == end)
49
{
50
return;
51
}
52
int mid = (start + end) >> 1;
53
merge_sort(start,mid);
54
merge_sort(mid,end);
55
merge(start,mid,end);
56
}
57
int main(void)
58

{
59
freopen("2299.in","r",stdin);
60
freopen("2299.out","w",stdout);
61
int n;
62
while(scanf("%d",&n),n)
63
{
64
total = 0;
65
for(int i = 0;i < n;i++)
66
{
67
scanf("%d",&num[i]);
68
}
69
merge_sort(0,n);
70
printf("%I64d\n",total);
71
}
72
return 0;
73
}
74