ACTime

let's start
随笔 - 10, 文章 - 22, 评论 - 2, 引用 - 0
数据加载中……

POJ 2299 Ultra-QuickSort

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

posted on 2009-12-17 14:00 ACTime 阅读(2677) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理