Minimum Inversion Number
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6743 Accepted Submission(s): 4112
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
Recommend
Ignatius.L
http://acm.hdu.edu.cn/showproblem.php?pid=1394
題意：
一個由0..n-1組成的序列，每次可以把隊首的元素移到隊尾，
求形成的n個序列中最小逆序對數目
思路：
如果求出第一種情況的逆序列，其他的可以通過遞推來搞出來，一開始是t[1],t[2],t[3]....t[N]
它的逆序列個數是N個，如果把t[1]放到t[N]後面，逆序列個數會減少t[1]個，相應會增加N-(t[1]+1)個
暴力法300ms：
[cpp]
#include<stdio.h>
int a[5555];
int main()
{
int n,i,j,ans=999999999;
while(scanf("%d",&n)!=EOF)
{
ans=999999999;
for(i=0;i<n;i++) scanf("%d",&a[i]);
int cnt=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j]) cnt++;
}
// printf("cnt=%d\n",cnt);
if(ans>cnt) ans=cnt;
for(i=0;i<n;i++)
{
cnt=cnt-a[i]+n-1-a[i];
if(ans>cnt) ans=cnt;
}
printf("%d\n",ans);
}
return 0;
}
#include<stdio.h>
int a[5555];
int main()
{
int n,i,j,ans=999999999;
while(scanf("%d",&n)!=EOF)
{
ans=999999999;
for(i=0;i<n;i++) scanf("%d",&a[i]);
int cnt=0;
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j]) cnt++;
}
// printf("cnt=%d\n",cnt);
if(ans>cnt) ans=cnt;
for(i=0;i<n;i++)
{
cnt=cnt-a[i]+n-1-a[i];
if(ans>cnt) ans=cnt;
}
printf("%d\n",ans);
}
return 0;
}
下面說一下線段樹的做法 31ms
用線段樹去求輸入序列的逆序數
方法：
把樹的葉子節點作為每個數的對應位置
枚舉到第i個數時，我們需要求出前i次插入的數中有多少個比a[i]大，
即去尋找已經插入的數中比a[i]大的數的個數 即查詢葉子節點a[i]到n的數的個數
[cpp]
#include<stdio.h>
int a[10000];
struct haha
{
int left;
int right;
int num;
}node[10000*4];
void build(int left,int right,int nd)
{
node[nd].left=left;
node[nd].right=right;
node[nd].num=0;
if(left==right)
{
return ;
}
int mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
}
int query(int left,int right,int nd)
{
int mid=(node[nd].left+node[nd].right)/2;
if(node[nd].left==left&&node[nd].right==right)
{
return node[nd].num;
}
if(right<=mid)
{
return query(left,right,nd*2);
}
else if(left>mid)
{
return query(left,right,nd*2+1);
}
else
{
return query(left,mid,nd*2)+query(mid+1,right,nd*2+1);
}
}
void update(int pos,int nd)
{
if(node[nd].left==node[nd].right) {node[nd].num++;return ;}
int mid=(node[nd].left+node[nd].right)/2;
if(pos<=mid) update(pos,nd*2);
else update(pos,nd*2+1);
node[nd].num=node[nd*2].num+node[nd*2+1].num;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
build(0,n-1,1);
int sum=0;
for(i=0;i<n;i++)
{
//printf("i=%d sum=%d\n",i,sum);
sum+=query(a[i],n-1,1);
// printf(">>>");
update(a[i],1);
}
// printf("%d\n",sum);
int ans=99999999;
if(ans>sum) ans=sum;
for(i=0;i<n;i++)
{
sum=sum-a[i]+n-1-a[i];
if(ans>sum) ans=sum;
}
printf("%d\n",ans);
}
return 0;
}
#include<stdio.h>
int a[10000];
struct haha
{
int left;
int right;
int num;
}node[10000*4];
void build(int left,int right,int nd)
{
node[nd].left=left;
node[nd].right=right;
node[nd].num=0;
if(left==right)
{
return ;
}
int mid=(left+right)/2;
build(left,mid,nd*2);
build(mid+1,right,nd*2+1);
}
int query(int left,int right,int nd)
{
int mid=(node[nd].left+node[nd].right)/2;
if(node[nd].left==left&&node[nd].right==right)
{
return node[nd].num;
}
if(right<=mid)
{
return query(left,right,nd*2);
}
else if(left>mid)
{
return query(left,right,nd*2+1);
}
else
{
return query(left,mid,nd*2)+query(mid+1,right,nd*2+1);
}
}
void update(int pos,int nd)
{
if(node[nd].left==node[nd].right) {node[nd].num++;return ;}
int mid=(node[nd].left+node[nd].right)/2;
if(pos<=mid) update(pos,nd*2);
else update(pos,nd*2+1);
node[nd].num=node[nd*2].num+node[nd*2+1].num;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
scanf("%d",&a[i]);
build(0,n-1,1);
int sum=0;
for(i=0;i<n;i++)
{
//printf("i=%d sum=%d\n",i,sum);
sum+=query(a[i],n-1,1);
// printf(">>>");
update(a[i],1);
}
// printf("%d\n",sum);
int ans=99999999;
if(ans>sum) ans=sum;
for(i=0;i<n;i++)
{
sum=sum-a[i]+n-1-a[i];
if(ans>sum) ans=sum;
}
printf("%d\n",ans);
}
return 0;
}
下面是歸並排序方法：
套用歸並排序模板
[cpp]
#include<stdio.h>
#include<malloc.h>
int ans,a[5050],b[5050];
void merge(int left,int mid,int right)
{
int i,j,cnt=0;
int *p;
p=(int *)malloc((right-left+1)*sizeof(int));
i=left;
j=mid+1;
while(i<=mid&&j<=right)//這時候i 和 j 指向的部分都排序完畢了 現在合並
{
if(a[i]<=a[j])
{
p[cnt++]=a[i];
i++;
}
else
{
p[cnt++]=a[j];
j++;
ans+=mid-i+1;//第i個比j大 由於i已經從小到大排過序了 那麼i+1到mid的也會比j大
}
}
while(i<=mid)
{
p[cnt++]=a[i++];
}
while(j<=right)
{
p[cnt++]=a[j++];
}
cnt=0;
for(i=left;i<=right;i++)
a[i]=p[cnt++];
free(p);
}
void merge_sort(int left,int right)
{
if(left<right) //長度大於1 這是個判斷不是循環
{
int mid;
mid=(left+right)/2;
merge_sort(left,mid);
merge_sort(mid+1,right);
merge(left,mid,right);
}
}
int main()
{
int n,i,j ;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++) {scanf("%d",&a[i]);b[i]=a[i];}
ans=0;
merge_sort(0,n-1);
//printf("ans=%d\n",ans);
int cnt=999999999;
if(cnt>ans) cnt=ans;
for(i=0;i<n;i++)
{
//printf("a[i]=%d\n",a[i]);
ans=ans-b[i]+n-1-b[i];
if(cnt>ans) cnt=ans;
}
printf("%d\n",cnt);
}
return 0;
}
#include<stdio.h>
#include<malloc.h>
int ans,a[5050],b[5050];
void merge(int left,int mid,int right)
{
int i,j,cnt=0;
int *p;
p=(int *)malloc((right-left+1)*sizeof(int));
i=left;
j=mid+1;
while(i<=mid&&j<=right)//這時候i 和 j 指向的部分都排序完畢了 現在合並
{
if(a[i]<=a[j])
{
p[cnt++]=a[i];
i++;
}
else
{
p[cnt++]=a[j];
j++;
ans+=mid-i+1;//第i個比j大 由於i已經從小到大排過序了 那麼i+1到mid的也會比j大
}
}
while(i<=mid)
{
p[cnt++]=a[i++];
}
while(j<=right)
{
p[cnt++]=a[j++];
}
cnt=0;
for(i=left;i<=right;i++)
a[i]=p[cnt++];
free(p);
}
void merge_sort(int left,int right)
{
if(left<right) //長度大於1 這是個判斷不是循環
{
int mid;
mid=(left+right)/2;
merge_sort(left,mid);
merge_sort(mid+1,right);
merge(left,mid,right);
}
}
int main()
{
int n,i,j ;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++) {scanf("%d",&a[i]);b[i]=a[i];}
ans=0;
merge_sort(0,n-1);
//printf("ans=%d\n",ans);
int cnt=999999999;
if(cnt>ans) cnt=ans;
for(i=0;i<n;i++)
{
//printf("a[i]=%d\n",a[i]);
ans=ans-b[i]+n-1-b[i];
if(cnt>ans) cnt=ans;
}
printf("%d\n",cnt);
}
return 0;
}
