首页 > 代码库 > xtu数据结构 C. Ultra-QuickSort
xtu数据结构 C. Ultra-QuickSort
C. Ultra-QuickSort
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
Ultra-QuickSort produces the output
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
解题：求逆序数，归并排序或者快排+树状数组都可以。坑爹的地方在于要使用long long ,害我WA了几次。逗比。。。。。。
树状数组+快速排序
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #define LL long long13 #define INF 0x3f3f3f14 using namespace std;15 const int maxn = 500002;16 struct node {17 int val,index;18 } p[maxn];19 LL tree[maxn];20 bool cmp(const node &x,const node &y) {21 return x.val > y.val;22 }23 int lowbit(int x) {24 return x&(-x);25 }26 void update(int x,int val) {27 for(int i = x; i < maxn; i += lowbit(i)) {28 tree[i] += val;29 }30 }31 LL sum(int x) {32 LL ans = 0;33 for(int i = x; i; i -= lowbit(i)) {34 ans += tree[i];35 }36 return ans;37 }38 int main() {39 int n,i;40 LL ans;41 while(scanf("%d",&n),n) {42 for(i = 0; i < n; i++) {43 scanf("%d",&p[i].val);44 p[i].index = i+1;45 }46 sort(p,p+n,cmp);47 memset(tree,0,sizeof(tree));48 int pre = INT_MIN;49 for(ans = i = 0; i < n; i++) {50 update(p[i].index,1);51 ans += sum(p[i].index-1);52 53 }54 printf("%lld\n",ans);55 }56 return 0;57 }
归并排序
1 #include <cstdio> 2 #define LL long long 3 LL sum,dt[500010]; 4 void mysort(int lft,int rht,int step){ 5 static LL temp[500010]; 6 int md = lft + (step>>1),i = 0,k = 0,j = 0; 7 while(lft + i < md && md + j < rht){ 8 if(dt[lft+i] > dt[md+j]){temp[k++] = dt[md+j];j++; 9 }else{temp[k++] = dt[lft+i];i++;sum += j;}10 }11 while(lft+i < md){temp[k++] = dt[lft+i];i++;sum += j;}12 while(md+j < rht){temp[k++] = dt[md+j];j++;}13 for(i = 0; i < k; i++) dt[lft+i] = temp[i];14 }15 void ms(int n){16 int len = 1,step = 2,m,i,u,v;17 sum = 0;18 while(len < n){len <<= 1;}19 m = len/step;20 while(step <= len){21 for(i = 0; i < m; i++){22 u = i*step;v = (i+1)*step;23 mysort(u,v>n?n:v,step);24 }25 step <<= 1;m = len/step;26 }27 }28 int main(){29 int n,i;30 while(scanf("%d",&n),n){31 for(i = 0; i < n; i++)32 scanf("%d",dt+i);33 ms(n);34 printf("%lld\n",sum);35 }36 return 0;37 }