Minimum Inversion Number

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19711    Accepted Submission(s): 11845 Problem Description 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 2   Sample Output 16   Author CHEN, Gaoli   Source ZOJ Monthly, January 2003  

题意

n个数分别是 0~n-1 ,给出这n个数的一个序列，可以做如题的转换， 问转换后最少有多少个逆序对

解题思路

用线段树维护当前区间出现过几个数， 插入a[i] 之前插入的比 a[i] 大的数的个数，即为 a[i]构成的逆序对的个数

先处理出初始序列的逆序对个数，然后从头枚举将a[i] 放 到最后，逆序对个数会变为几 。

a[i]一开始在第一个位置，比他小的肯定都在其后面，产生a[i]个逆序对  所以将a[i]放到最后需 要  加上多产生的(n-a[i]-1)个逆序对

再减去a[i]放最后之前构成逆序对的个数

代码

#include <iostream> #include <cstdio> #include <map> #include <cmath> #include <string.h> #include <algorithm> #include <set> #include <sstream> #include <vector> #include <queue> #include <stack> using namespace std; const int maxn = 5000*4; const int INF = 0x3f3f3f3f; struct node{ int l,r; int sum;///区间l-r有几个数了 }tree[maxn]; void buildtree(int node,int b,int e){ int mid = (b+e)/2; tree[node].l = b; tree[node].r = e; tree[node].sum = 0; if(b==e) return; if(b <= mid) buildtree(node*2,b,mid); if(e > mid) buildtree(node*2+1,mid+1,e); } void update(int node,int ql,int qr){ if(ql <= tree[node].l && qr >= tree[node].r){ tree[node].sum ++; return; } int mid = (tree[node].l + tree[node].r)/2; if(ql <= mid) update(node*2,ql,qr); if(qr > mid) update(node*2+1,ql,qr); tree[node].sum = tree[node*2].sum + tree[node*2+1].sum; } int query(int node,int ql,int qr){ int ans1 = 0,ans2 = 0; if(ql <= tree[node].l && qr >= tree[node].r) return tree[node].sum; int mid = (tree[node].l + tree[node].r)/2; if(ql <= mid) ans1 = query(node*2,ql,qr); if(qr > mid) ans2 = query(node*2+1,ql,qr); return ans1+ans2; } int main(){ int n; int a[maxn]; while(scanf("%d",&n) != EOF){ int sum = 0;///初始情况下，逆序对的个数 buildtree(1,0,n-1); for(int i =0;i<n;++i){ scanf("%d",&a[i]); sum += query(1,a[i],n-1);///在他之前插入的比他大的数有几个 update(1,a[i],a[i]); } int res = sum; for(int i = 0; i < n; ++i){///将a[i]放到后面 ///a[i]一开始在第一个位置，比他小的肯定都在其后面，产生a[i]个逆序对 ///所以将a[i]放到最后需要 ///加上多产生的(n-a[i]-1)个逆序对再减去a[i]放最后之前构成逆序对的个数 sum += (n-a[i]-1) - a[i]; res = min(res,sum); } printf("%d\n",res); } return 0; }