题目链接: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 }
的