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 }