首页 > 代码库 > HDU 2689 Sort it【树状数组】

HDU 2689 Sort it【树状数组】

2024-10-18 09:32:39   214人阅读

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.
 

 

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
ZJFC 2009-3 Programming Contest
 

 

Recommend
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2689
分析：好吧，我智障了，听说有种很快的写法，但好像跑的速度没我快？应该是我代码跑的最快吧，写法也是最复杂的，这题我是用树状数组乱搞的，反正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 node39 {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 }

 

HDU 2689 Sort it【树状数组】


联系
我们