首页 > 代码库 > hdu 1394 Minimum Inversion Number_归并排序

hdu 1394 Minimum Inversion Number_归并排序

题目链接

题意:给你一个有0--n-1数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!

思路:可以暴力,树状树状,线段树,归并排序,这里只给出,暴力和归并

//暴力

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 5010
int a[N];
long long sum,ans; 
int main(int argc, char** argv) {
    int n,i,k,j,ans;
    while(scanf("%d",&n)!=EOF){
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sum=0;
        for(i=0;i<n;i++){
            k=0;
            for(j=i+1;j<n;j++)
                if(a[i]>a[j])
                    k++;
            sum+=k;
        }
        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 <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 5010
int a[MAXN],c[MAXN],x[MAXN],cnt;
long long sum,ans; 
void MergeSort(int l,int r){
	int mid,i,j,tmp;
	if(r>l+1){
		mid=(l+r)>>1;
		MergeSort(l,mid);
		MergeSort(mid,r);
		tmp=l;
		for(i=l,j=mid;i<mid&&j<r;){
			if(a[i]>a[j]){
				c[tmp++]=a[j++];
				cnt+=mid-i;
			}else
				c[tmp++]=a[i++];
		}
		if(j<r)
			while(j<r) c[tmp++]=a[j++];
		else
			while(i<mid) c[tmp++]=a[i++];
		for(i=l;i<r;i++)
			a[i]=c[i];
	}
}
int main(int argc, char** argv) {
    int n,i,k,j,ans;
    while(scanf("%d",&n)!=EOF){
    	cnt=0;
        for(i=0;i<n;i++){
            scanf("%d",&x[i]);
            a[i]=x[i];
        }
        MergeSort(0,n);
        ans=cnt;
        for(i=0;i<n;i++){
            cnt=cnt-x[i]+(n-1)-x[i];
            if(ans>cnt)
                ans=cnt;
        }
        printf("%d\n",ans);
        
    }
    return 0;
}