首页 > 代码库 > C - Minimum Inversion Number
C - Minimum Inversion Number
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.
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
1 #include"iostream" 2 #include"cstdio" 3 #include"string" 4 using namespace std; 5 #define lson l,mid,rt<<1 6 #define rson mid+1,r,rt<<1|1 7 #define MAX 5004 8 int s[MAX]; 9 int sum; 10 struct node 11 { 12 int l; 13 int r; 14 int va; 15 }tree[MAX<<2]; 16 void build(int l,int r,int rt) 17 { 18 tree[rt].l=l; 19 tree[rt].r=r; 20 tree[rt].va=0; 21 if(tree[rt].l==tree[rt].r) 22 return ; 23 int mid=(tree[rt].l+tree[rt].r)>>1; 24 build(lson); 25 build(rson); 26 } 27 void updata(int x,int rt) 28 { 29 if(tree[rt].l==tree[rt].r) 30 { 31 tree[rt].va=1; 32 return; 33 } 34 int mid=(tree[rt].l+tree[rt].r)>>1; 35 if(x<=mid) 36 updata(x,rt<<1); 37 else 38 updata(x,rt<<1|1); 39 tree[rt].va=tree[rt<<1].va+tree[rt<<1|1].va; 40 } 41 void query(int l,int r,int rt) 42 { 43 if(tree[rt].l==l&&tree[rt].r==r) 44 { 45 sum+=tree[rt].va; 46 return; 47 } 48 int mid=(tree[rt].l+tree[rt].r)>>1; 49 if(r<mid) 50 query(l,r,rt<<1); 51 else if(l>mid) 52 query(l,r,rt<<1|1); 53 else 54 { 55 query(lson); 56 query(rson); 57 } 58 } 59 int main() 60 { 61 int n,i,t,m; 62 while(scanf("%d",&n)!=EOF) 63 { 64 build(0,n-1,1); 65 sum=0; 66 for(i=0;i<n;i++) 67 { 68 scanf("%d",&s[i]); 69 query(s[i],n-1,1); 70 updata(s[i],1); 71 } 72 m=sum; 73 for(i=0;i<n;i++) 74 { 75 sum=sum-s[i]+n-1-s[i]; 76 if(m>sum) 77 m=sum; 78 } 79 printf("%d\n",m); 80 } 81 return 0; 82 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。