首页 > 代码库 > C - Minimum Inversion Number

C - Minimum Inversion Number

2024-07-02 20:00:21   223人阅读

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
 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 }
View Code

 

 


联系
我们