2010年02月08日星期一.sgu180 归并排序求逆序对
归并排序求逆序对
举例说明：
在归并排序合并两个有序链时
i为第一链的指针，j为第二个的
以下部分需要等宽字体才能正确查看
1 4 5 9↑ 2 4 7 7↑ i++--------- * * *1 4 5 9 ↑ 2 4 7 7↑ j++,res += 3---------1 4 5 9 ↑ 2 4 7 7 ↑ i++--------- * *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 2---------1 4 5 9 ↑ 2 4 7 7 ↑ i++--------- *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 1--------- *1 4 5 9 ↑ 2 4 7 7 ↑ j++,res += 1---------1 4 5 9 ↑ 2 4 7 7 ↑ ---------之后将两个链中没处理完的添加到buf中
1
2 const int N = 65600;
3 int n,a[N],buf[N];
4 LL res;
5
6 void mergesort(int beg,int end)
7 {
8 if (end <= beg + 1) {
9 if (a[beg] > a[end]) {
10 res ++;
11 swap(a[beg],a[end]);
12 }
13 return;
14 }
15 int mid = (beg + end)/2,i,j,k;
16 mergesort(beg,mid);
17 mergesort(mid+1,end);
18 for (i = beg,j = mid + 1,k = beg;i <= mid && j <= end;) {
19 if (a[i] > a[j]) {
20 res += mid + 1 - i;
21 buf[k++] = a[j++];
22 }else if (a[i] <= a[j]) {
23 buf[k++] = a[i++];
24 }
25 }
26 while (i <= mid) { buf[k++] = a[i++]; }
27 while (j <= end) { buf[k++] = a[j++]; }
28 for (i = beg;i <= end;i++) { a[i] = buf[i]; }
29 }
30
31 int main()
32 {
33 int i,j,k;
34 scanf("%d",&n);
35 for (i = 0;i < n;i++) {
36 scanf("%d",a + i);
37 }
38 mergesort(0,n-1);
39 cout << res << endl;
40 //printf("%d\n",res);
41 return 0;
42 }