Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
---|---|---|
Total Submissions: 38258 | Accepted: 13784 |
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence 9 1 0 5 4 , Ultra-QuickSort produces the output 0 1 4 5 9 . Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 -- the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
Source
代码:
1 //离散化+树状数组
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define maxn 500000
6 struct node
7 {
8 int val;
9 int id;
10 };
11 node stu[maxn+5];
12 int n;
13 __int64 cnt;
14 int bb[maxn+5];
15 int lowbit(int x)
16 {
17 return x&(-x);
18 }
19 void ope(int x)
20 {
21 while(x<=n)
22 {
23 bb[x]++;
24 x+=lowbit(x);
25 }
26 }
27 int sum(int x)
28 {
29 int ans=0;
30 while(x>0)
31 {
32 ans+=bb[x];
33 x-=lowbit(x);
34 }
35 return ans;
36 }
37 int cmp(const void *a ,const void *b)
38 {
39 return (*(node *)a).val -(*(node *)b).val;
40 }
41 int main()
42 {
43 int i;
44 while(scanf("%d",&n),n)
45 {
46 memset(bb,0,sizeof(int)*(n+1));
47 for(i=0;i<n;i++)
48 {
49 scanf("%d",&stu[i].val);
50 stu[i].id=i+1;
51 }
52 qsort(stu,n,sizeof(stu[0]),cmp);
53 cnt=0;
54 for(i=0;i<n;i++)
55 {
56 cnt+=sum(n)-sum(stu[i].id);
57 ope(stu[i].id);
58 }
59 printf("%I64d\n",cnt);
60 }
61 return 0;
62 }
归并排序:
代码:
1 //归并排序求逆序数
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #define maxn 500000
6 int cc[maxn+5];
7 int aa[maxn+5];
8 __int64 cnt;
9 void merge(int low ,int mid,int hig)
10 {
11 int i,j,k;
12 i=low;
13 j=mid;
14 k=0;
15 while(i<mid&&j<hig)
16 {
17 if(aa[i]>aa[j])
18 {
19 cc[k++]=aa[j++];
20 cnt+=mid-i;
21 }
22 else
23 cc[k++]=aa[i++];
24 }
25 while(i<mid)
26 cc[k++]=aa[i++];
27 while(j<hig)
28 cc[k++]=aa[j++];
29 for(k=0,i=low;i<hig;i++)
30 aa[i]=cc[k++];
31 }
32 void merge_sort(int st,int en)
33 {
34 int mid;
35 if(st+1<en)
36 {
37 mid=st+(en-st)/2;
38 merge_sort(st,mid);
39 merge_sort(mid,en);
40 merge(st,mid,en);
41 }
42 }
43 int main()
44 {
45 int n,i;
46 while(scanf("%d",&n),n)
47 {
48 cnt=0;
49 for(i=0;i<n;i++)
50 scanf("%d",aa+i);
51 merge_sort(0,n);
52 printf("%I64d\n",cnt);
53 }
54 return 0;
55 }
非递归归并排序: 代码:
1 //归并排序求逆序数
2 #include<stdio.h>
3 #include<string.h>
4 #include<stdlib.h>
5 #define maxn 500000
6 int cc[maxn+5];
7 int aa[maxn+5];
8 __int64 cnt;
9 void merge(int low ,int mid,int hig)
10 {
11 int i,j,k;
12 i=low;
13 j=mid;
14 k=0;
15 while(i<mid&&j<hig)
16 {
17 if(aa[i]>aa[j])
18 {
19 cc[k++]=aa[j++];
20 cnt+=mid-i;
21 }
22 else
23 cc[k++]=aa[i++];
24 }
25 while(i<mid)
26 cc[k++]=aa[i++];
27 while(j<hig)
28 cc[k++]=aa[j++];
29 for(k=0,i=low;i<hig;i++)
30 aa[i]=cc[k++];
31 }
32 //void merge_sort(int st,int en)
33 //{
34 // int mid;
35 // if(st+1<en)
36 // {
37 // mid=st+(en-st)/2;
38 // merge_sort(st,mid);
39 // merge_sort(mid,en);
40 // merge(st,mid,en);
41 // }
42 //}
43 void merge_sort(int st,int en)
44 {
45 int s,t,i;
46 t=1;
47 while(t<=(en-st))
48 {
49 s=t;
50 t<<=1;
51 i=st;
52 while(i+t<=en)
53 {
54 merge(i,i+s,i+t);
55 i+=t;
56 }
57 if(i+s<en)
58 merge(i,i+s,en);
59 }
60 if(i+s<en)
61 merge(i,i+s,en);
62 }
63 int main()
64 {
65 int n,i;
66 while(scanf("%d",&n),n)
67 {
68 cnt=0;
69 for(i=0;i<n;i++)
70 scanf("%d",aa+i);
71 merge_sort(0,n);
72 printf("%I64d\n",cnt);
73 }
74 return 0;
75 }