题目链接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
题目描述：求冒泡排序的交换次数
所用算法：用归并排序，求逆序数的个数
提交情况：1次tle(直接冒泡排序n^2的复杂度，对于5000000的数据量，必然超时)，1次wa（统计个数时整数溢出了），1a
心得体会：初看题目很简单，没有往数据量方面想，直接冒泡计数提交，然后看着poj上一直running&&judging直到tle, 时限7000ms呀。没做过逆序数的类似问题，而且题目本身分类也在排序那，然后考虑是不是能快排一下，比较排序前和排序后各个数的位置。考虑再三，发现解决不了。去论坛上瞄了一眼，看到可以用逆序数解，于是百度＋算法导论，学到了如何用归并排序计算逆序数的数目，写成程序，中间还出现了一次wa，然后就ac了。我在看算法导论时，因为merge在书一开始讲的，想平时排序都是快排为主流，就没有仔细想过merge可能的变种，这道题充分印证了，即使merge本身可能用的不多，但分冶的思想却是无所不在
类似题目：poj1804
1 #include<iostream>
2 #include<stdio.h>
3 using namespace std;
4
5 int num[500010];
6 int left_t[500010];
7 int right_t[500010];
8
9 long long count=0;
10
11 void merge(int a[],int p,int q,int r)
12 {
13 int n1=q-p+1;
14 int n2=r-q;
15 for(int i=1;i<=n1;i++)
16 {
17 left_t[i]=a[p+i-1];
18 }
19 for(int i=1;i<=n2;i++)
20 {
21 right_t[i]=a[q+i];
22 }
23 left_t[n1+1]=0x7fffffff;
24 right_t[n2+1]=0x7fffffff;
25
26 int i=1;
27 int j=1;
28 for(int k=p;k<=r;k++)
29 {
30 if(left_t[i]<=right_t[j])
31 {
32 a[k]=left_t[i];
33 i=i+1;
34 }
35 else
36 {
37 a[k]=right_t[j];
38 j=j+1;
39 count+=n1-i+1;
40 }
41 }
42 }
43
44 void merge_sort(int a[],int p,int r)
45 {
46 if(p<r)
47 {
48 int q=(p+r)/2;
49 merge_sort(a,p,q);
50 merge_sort(a,q+1,r);
51 merge(a,p,q,r);
52 }
53 }
54
55 int main()
56 {
57 int n;
58 scanf("%d",&n);
59 while(n!=0)
60 {
61 for(int i=0;i<n;i++)
62 {
63 scanf("%d",&num[i]);
64 }
65 merge_sort(num,0,n-1);
66 printf("%lld\n",count);
67 count=0;
68 scanf("%d",&n);
69 }
70 }
的