本文主要是介绍HDU 1394 Minimum Inversion Number（线段树求逆序数），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：HDU 1394
这题可以用线段树来求逆序数。
这题的维护信息为每个数是否已经出现。每次输入后，都从该点的值到n-1进行查询，每次发现出现了一个数，由于是从该数的后面开始找的，这个数肯定是比该数大的。那就是一对逆序数，然后逆序数+1.最后求完所有的逆序数之后，剩下的就可以递推出来了。因为假如目前的第一个数是x，那当把他放到最后面的时候，少的逆序数是本来后面比他小的数的个数。多的逆序数就是放到后面后前面比他大的数的个数。因为所有数都是从0到n-1.所以比他小的数就是x，比他大的数就是n-1-x。这样的话每次的逆序数都可以用O(1)的时间计算出来。然后找最小的时候就可以了。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <stack>
using namespace std;
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1
const int MAXN=6e3;
int sum[MAXN<<2], a[MAXN];
void PushUp(int rt)
{sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l, int r, int rt)
{sum[rt]=0;if(l==r){return ;}int mid=l+r>>1;build(lson);build(rson);
}
void update(int p, int l, int r, int rt)
{if(l==r){sum[rt]++;return ;}int mid=l+r>>1;if(p<=mid) update(p,lson);else update(p,rson);PushUp(rt);
}
int query(int ll, int rr, int l, int r, int rt)
{if(ll<=l&&rr>=r){return sum[rt];}int mid=l+r>>1;int ans=0;if(ll<=mid) ans+=query(ll,rr,lson);if(rr>mid) ans+=query(ll,rr,rson);return ans;
}
int main()
{int n, i, ans, y;while(scanf("%d",&n)!=EOF){build(0,n-1,1);ans=0;for(i=0; i<n; i++){scanf("%d",&a[i]);ans+=query(a[i],n-1,0,n-1,1);update(a[i],0,n-1,1);}y=ans;for(i=0;i<n;i++){y+=n-1-2*a[i];ans=min(ans,y);}printf("%d\n",ans);}return 0;
}
这篇关于HDU 1394 Minimum Inversion Number（线段树求逆序数）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
