E. Ultra-QuickSort

Time Limit: 7000ms

Case Time Limit: 7000ms

Memory Limit: 65536KB

64-bit integer IO format: 

%lld      Java class name: 

Main

Submit 

Status 

PID: 2418

Font Size: 

+ 

-

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

59105431230

Sample Output

60

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include <algorithm>

using namespace std;

struct node

{

int origin;

int set;

}a[500005]; 

int n;

int c[500005],sa[500005];

bool cmp(const node &aa,const node &bb)

{

return aa.origin<bb.origin;

}

int lowbit(int x)

{

return x&(-x);

}

void update(int i,int x)

{

while(i<=n)

{

c[i]+=x;

i+=lowbit(i);

}

}

int getsum(int i)

{

int sum=0;

while(i>0)

{

sum+=c[i];

i-=lowbit(i);

}

return sum;

}

int main()

{

int i;

long long ss;

while(scanf("%d",&n)&&n!=0)

{

ss=0;

sort(a+1,a+n+1,cmp);

for(i=1;i<=n;i++)

{

scanf("%d",&a[i].origin);

a[i].set=i;

}

for(i=1;i<=n;i++)

sa[a[i].set]=i;

memset(c,0,sizeof(c));

for(i=1;i<=n;i++)

{

update(sa[i],1);

ss=ss+i-getsum(sa[i]);

}

printf("%lld\n",ss);

}

}

 ————————————————————————————————

细看一下，网上的微博实在坑。。。坑 坑。。。。。

#include<stdio.h> #include<stdlib.h> #include<string.h> struct node { int origin; int set; }a[500005]; int n; int c[500005]; int cmp(const void *aa,const void *bb) { node *a=(node *)aa; node *b=(node *)bb; return a->origin-b->origin; } int lowbit(int x) { return x&(-x); } void update(int i,int x) { while(i<=n) { c[i]+=x; i+=lowbit(i); } } int getsum(int i) { int sum=0; while(i>0) { sum+=c[i]; i-=lowbit(i); } return sum; } int main() { int i; long long ss; while(scanf("%d",&n)&&n!=0) { ss=0; for(i=1;i<=n;i++) { scanf("%d",&a[i].origin); a[i].set=i; } qsort(a+1,n,sizeof(a[0]),cmp); memset(c,0,sizeof(c)); for(i=1;i<=n;i++) { update(a[i].set,1); ss=ss+i-getsum(a[i].set); } printf("%lld\n",ss); } }

——————————————————————————————————

下面这个是参考网上写的，发现差别没有

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<string.h>
4. struct node
5. {
6.     int origin;
7.     int set;
8. }a[500005];
9. int n;
10. int c[500005],sa[500005];
11. int cmp(const void *aa,const void *bb)
12. {
13.     node *a=(node *)aa;
14.     node *b=(node *)bb;
15.     return a->origin-b->origin;
16. }
17. int lowbit(int x)
18. {
19.     return x&(-x);
20. }
21. void update(int i,int x)
22. {
23.     while(i<=n)
24.     {
25.         c[i]+=x;
26.         i+=lowbit(i);
27.     }
28. }
29. int getsum(int i)
30. {
31.     int sum=0;
32.     while(i>0)
33.     {
34.         sum+=c[i];
35.         i-=lowbit(i);
36.     }
37.     return sum;
38. }
39. int main()
40. {
41.     int i;
42.     long long ss;
43.     while(scanf("%d",&n)&&n!=0)
44.     {
45.         ss=0;
46.     for(i=1;i<=n;i++)
47.     {
48.     scanf("%d",&a[i].origin);
49.     a[i].set=i;
50. }
51.     qsort(a+1,n,sizeof(a[0]),cmp);
52. for(i=1;i<=n;i++) //没错，就是这里，完全没有必要的一个语句，不知道那个大神加了上去， 然后同学们就疯狂的参考，转载
53. sa[a[i].set]=i;
54. memset(c,0,sizeof(c));
55. for(i=1;i<=n;i++)
56. {
57.     update(sa[i],1);
58.     ss=ss+i-getsum(sa[i]);
59. }
60. printf("%lld\n",ss);
61. }
62. }
63.     
64.         

好吧，我承认是我看走眼，其实网上那个资料是用原理来的，我是凑巧结果对了