Sort it
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4672 Accepted Submission(s): 3244
Problem Description
You want to processe a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. Then how many times it need.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.
For example, 1 2 3 5 4, we only need one operation : swap 5 and 4.
Input
The input consists of a number of test cases. Each case consists of two lines: the first line contains a positive integer n (n <= 1000); the next line contains a permutation of the n integers from 1 to n.
Output
For each case, output the minimum times need to sort it in ascending order on a single line.
Sample Input
3
1 2 3
4
4 3 2 1
Sample Output
0
6
Author
WhereIsHeroFrom
Source
Recommend
分析：好吧，我智障了，听说有种很快的写法，但好像跑的速度没我快？应该是我代码跑的最快吧，写法也是最复杂的，这题我是用树状数组乱搞的，反正15ms，相当快啊！
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 inline int read() 5 { 6 int x=0,f=1; 7 char ch=getchar(); 8 while(ch<'0'||ch>'9') 9 { 10 if(ch=='-') 11 f=-1; 12 ch=getchar(); 13 } 14 while(ch>='0'&&ch<='9') 15 { 16 x=x*10+ch-'0'; 17 ch=getchar(); 18 } 19 return x*f; 20 } 21 inline void write(int x) 22 { 23 if(x<0) 24 { 25 putchar('-'); 26 x=-x; 27 } 28 if(x>9) 29 { 30 write(x/10); 31 } 32 putchar(x%10+'0'); 33 } 34 const int N=1001; 35 int n; 36 int num[N]; 37 int c[N]; 38 struct node 39 { 40 int x; 41 int id; 42 }q[N] ; 43 bool cmp(node a,node b) 44 { 45 return a.x<b.x; 46 } 47 int lowbit(int x) 48 { 49 return x&(-x); 50 } 51 int getsum(int x) 52 { 53 int s=0; 54 while(x>0) 55 { 56 s+=c[x]; 57 x-=lowbit(x); 58 } 59 return s; 60 } 61 void add(int x,int y) 62 { 63 while(x<=n) 64 { 65 c[x]+=y; 66 x+=lowbit(x); 67 } 68 } 69 int main() 70 { 71 while(scanf("%d",&n)!=EOF) 72 { 73 memset(c,0,sizeof(c)); 74 memset(num,0,sizeof(num)); 75 for(int i=1;i<=n;i++) 76 { 77 scanf("%d",&q[i].x); 78 q[i].id=i; 79 } 80 sort(q+1,q+1+n,cmp); 81 for(int i=1;i<=n;i++) 82 { 83 num[q[i].id]=i; 84 } 85 int sum = 0; 86 for(int i=1;i<=n;i++) 87 { 88 add(num[i],1); 89 sum+=getsum(n)-getsum(num[i]); 90 } 91 printf("%d\n",sum); 92 } 93 return 0; 94 }
