Ultra-QuickSort
Time Limit: 7000MS | Memory Limit: 65536K | |
Total Submissions: 27736 | Accepted: 9946 |
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.
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.
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
Source
这就是题求逆序数的题:方法有多种,最简单的用归并排序
我用的是树状数组;题目明显直接建树是不行的,因此得将其数变小,因此,用来两次快排
有个陷阱,和数据会超,得用long long 我就是因为这被WA了几次
#include<cstdio> #include<algorithm> #include<cstring> #define N 500004 using namespace std; int M; long long f[N]; int s[N]; class node { public: int num; int p; }root[N]; int lowbit(int n) { return n&(-n); } void add(int s) { while(s<=M) { f[s]++; s+=lowbit(s); } } long long query(int num) { long long sum=0; while(num>0) { sum+=f[num]; num-=lowbit(num); } return sum; } bool cmp(node a,node b) { return a.num<b.num; } bool cmpp(node a,node b) { return a.p<b.p; } int main() { int a; while(scanf("%d",&M)&&M) { memset(f,0,sizeof(f)); long long sum=0; for(int i=0;i<M;i++) { scanf("%d",&root[i].num); root[i].p=i; } stable_sort(root,root+M,cmp); for(int i=0;i<M;i++) root[i].num=i+1; stable_sort(root,root+M,cmpp); for(int i=0;i<M;i++) { add(root[i].num); sum+=query(M)-query(root[i].num); } printf("%lld\n",sum); } }