題目鏈接：http://acm.pku.edu.cn/JudgeOnline/problem?id=2299
題目描述：求冒泡排序的交換次數(shù)
所用算法：用歸并排序，求逆序數(shù)的個數(shù)
提交情況：1次tle(直接冒泡排序n^2的復(fù)雜度，對于5000000的數(shù)據(jù)量，必然超時)，1次wa（統(tǒng)計個數(shù)時整數(shù)溢出了），1a
心得體會：初看題目很簡單，沒有往數(shù)據(jù)量方面想，直接冒泡計數(shù)提交，然后看著poj上一直running&&judging直到tle, 時限7000ms呀。沒做過逆序數(shù)的類似問題，而且題目本身分類也在排序那，然后考慮是不是能快排一下，比較排序前和排序后各個數(shù)的位置。考慮再三，發(fā)現(xiàn)解決不了。去論壇上瞄了一眼，看到可以用逆序數(shù)解，于是百度＋算法導(dǎo)論，學(xué)到了如何用歸并排序計算逆序數(shù)的數(shù)目，寫成程序，中間還出現(xiàn)了一次wa，然后就ac了。我在看算法導(dǎo)論時，因為merge在書一開始講的，想平時排序都是快排為主流，就沒有仔細想過merge可能的變種，這道題充分印證了，即使merge本身可能用的不多，但分冶的思想?yún)s是無所不在
類似題目：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 }
的