Minimum Inversion Number HDU 1394

本文主要是介绍Minimum Inversion Number HDU 1394，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

用树状数组求逆序数。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 5004
int a[maxn];
int n=maxn;
int lowbit(int i)
{return i&(-i);
}
int Sum(int i)
{int sum=0;while(i>=1){sum+=a[i];i-=lowbit(i);}return sum;
}
void Update(int i,int tem)
{while(i<=n){a[i]+=tem;i+=lowbit(i);}
}
int main()
{int m,i;int sum,min,k;int b[maxn],c[maxn];while(scanf("%d",&m)!=EOF){memset(a,0,sizeof(a));memset(b,0,sizeof(b));memset(c,0,sizeof(c));for(i=1;i<=m;i++){scanf("%d",&b[i]);//用b接受原数据b[i]++;//防止输入0，造成死循环。}sum=0;for(i=1;i<=m;i++){Update(b[i],1);//离散化数据sum+=Sum(maxn)-Sum(b[i]);//求出比这个数小的}min=sum;for(i=1;i<=m;i++)//把第一个数变换到最后.//Sum(b[i]-1)为变换之前第一个数构成的逆序数量，(m-1-Sum(b[i]-1)为变换之后增加的逆序的数量。{k=sum-Sum(b[i]-1)+(m-1-Sum(b[i]-1));if(k<min)min=k;sum=k;}	printf("%d\n",min);}return 0;
}

这篇关于Minimum Inversion Number HDU 1394的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---