[关闭]
@Chilling 2016-08-19T18:02:32.000000Z 字数 1523 阅读 1040

swustoj-1360: Ultra-QuickSort(归并排序)


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

  1. #include<stdio.h>
  2. int a[500005],b[500005];
  3. long long ans;
  4. void merge(int m[],int temp[],int start,int mid,int end)
  5. {
  6. int i=start,j=mid+1,cnt=start;
  7. while(i<=mid&&j<=end)
  8. {
  9. if(m[i]<=m[j])
  10. temp[cnt++]=m[i++];
  11. else
  12. {
  13. temp[cnt++]=m[j++];
  14. ans=ans+mid-i+1;
  15. }
  16. }
  17. while(i<=mid)
  18. temp[cnt++]=m[i++];
  19. while(j<=end)
  20. temp[cnt++]=m[j++];
  21. for(i=start;i<=end;i++)
  22. m[i]=temp[i];
  23. }
  24. void mergesort(int m[],int temp[],int start,int end)
  25. {
  26. if(start==end)return;
  27. int mid=(start+end)/2;
  28. mergesort(m,temp,start,mid);
  29. mergesort(m,temp,mid+1,end);
  30. merge(m,temp,start,mid,end);
  31. }
  32. int main()
  33. {
  34. int n,i;
  35. while(scanf("%d",&n),n)
  36. {
  37. ans=0;
  38. for(i=0;i<n;i++)
  39. scanf("%d",&a[i]);
  40. mergesort(a,b,0,n-1);
  41. printf("%lld\n",ans);
  42. }
  43. return 0;
  44. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注