The inversion number of a given number sequence a1, a2, ..., an is the number of pairs (ai, aj) that satisfy i < j and ai > aj. For a given sequence of numbers a1, a2, ..., an, if we move the first m >= 0 numbers to the end of the seqence, we will obtain another sequence. There are totally n such sequences as the following: a1, a2, ..., an-1, an (where m = 0 - the initial seqence) a2, a3, ..., an, a1 (where m = 1) a3, a4, ..., an, a1, a2 (where m = 2) ... an, a1, a2, ..., an-1 (where m = n-1) You are asked to write a program to find the minimum inversion number out of the above sequences.
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 <= 5000); the next line contains a permutation of the n integers from 0 to n-1.
Output
For each case, output the minimum inversion number on a single line.
Sample Input
10 1 3 6 9 0 8 5 7 4 2Sample Output
16题意：
序列0~n-1这n个数，求
a1, a2, ..., an-1, an (where m = 0 - the initial seqence) a2, a3, ..., an, a1 (where m = 1) a3, a4, ..., an, a1, a2 (where m = 2) ... an, a1, a2, ..., an-1 (where m = n-1) 每种序列的逆序对数量的最小值
思路：首先求出原来序列的逆序对的数量，每次把第一个数放到最后边逆序对变化量：n-a[i]-(a[i]-1)
为什么是这个：在第一个位置的数，比它小的有a[i]-1个，比它大的有n-a[i]个，所以放到最后边对原来序列逆序对的贡献值就是：n-a[i]-(a[i]-1)
代码：
import java.util.Arrays; import java.util.Scanner; public class Main{ static int n; static final int max=5005; static int tree[]=new int[max<<2]; static int arr[]=new int[max<<2]; public static void update(int node,int l,int r,int a,int b){ if(l==a&&r==b){ tree[node]+=1; return; } int mid=(l+r)>>1; if(a<=mid) update(node<<1,l,mid,a,b); if(b>mid) update(node<<1|1,mid+1,r,a,b); tree[node]=tree[node<<1]+tree[node<<1|1]; } public static int query(int node,int l,int r,int a,int b){ if(l>=a&&r<=b){ return tree[node]; } int mid=(l+r)>>1; if(b<=mid) return query(node<<1,l,mid,a,b); else if(a>mid) return query(node<<1|1,mid+1,r,a,b); else return query(node<<1,l,mid,a,b)+query(node<<1|1,mid+1,r,a,b); } public static void main(String[] args) { Scanner scan=new Scanner(System.in); while(scan.hasNext()){ n=scan.nextInt(); Arrays.fill(tree, 0); for(int i=1;i<=n;i++){ arr[i]=scan.nextInt()+1;//数组值加一，和update，query的了l，r对应起来 } int sum=0; for(int i=1;i<=n;i++){ int a=arr[i]; update(1,1,n,a,a); sum+=(i-query(1,1,n,1,a)); } int ans=sum; for(int i=1;i<n;i++){ sum=sum+(n-arr[i])-(arr[i]-1); if(sum<ans) ans=sum; } System.out.println(ans); } } }
