The answer is the number of inversions in the array, which is the number of pairs i,j such that i < j and a[i] > a[j]. Counting this is a fairly classical problem with many solutions such as using data structures such as Balanced Trees or Binary Indexed Trees. Another particularly elegant solution involves modifying merge sort to count the number of inversions when merging the two sorted halves in the algorithm.
-
-
Save liuyuuan/3496909 to your computer and use it in GitHub Desktop.
Insertion Sort Solutions (InterviewStreet CodeSprint Fall 2011)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<iostream> | |
| #include<stdio.h> | |
| #include<string.h> | |
| using namespace std ; | |
| #define MAXN 100002 | |
| #define MAX 1000002 | |
| int n,a[MAXN],c[MAX] ; | |
| int main() | |
| { | |
| int runs ; | |
| scanf("%d",&runs) ; | |
| while(runs--) | |
| { | |
| scanf("%d",&n) ; | |
| for(int i = 0;i < n;i++) scanf("%d",&a[i]) ; | |
| long long ret = 1LL * n * (n - 1) / 2 ; | |
| memset(c,0,sizeof c) ; | |
| for(int i = 0;i < n;i++) | |
| { | |
| for(int j = a[i];j > 0;j -= j & -j) ret -= c[j] ; | |
| for(int j = a[i];j < MAX;j += j & -j) c[j]++ ; | |
| } | |
| cout << ret << endl ; | |
| } | |
| return 0 ; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment