本文主要是介绍http://acm.hdu.edu.cn/showproblem.php?pid=1394，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
树状数组求逆序数的应用。。这一题设计的非常巧妙。。。下面说一下题意。。给定一组数，然后依次的挪动该组数的元素共得到n种序列。求这n中序列中逆序数最少的个数。。。杯具的是我竟然把树状数组和一般的数组弄混淆了。。这里要特别注意。。。不过值得一提的是竟然rank1，(*^__^*) 嘻嘻……
AC代码：
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define N 5005
using namespace std;
int s[N];
int kp[N];
int n;
int lowbit(int x)
{return x&(-x);}
void update(int x)
{ while(x<=n){ s[x]++; x+=lowbit(x);}
}
int Quary(int x)
{ int sum=0;while(x>0){ sum+=s[x];x-=lowbit(x);}return sum;
}
int main()
{ while(~scanf("%d",&n)){ int res=0;memset(s,0,sizeof(s));memset(kp,0,sizeof(kp));for(int i=1;i<=n;++i){ scanf("%d",&kp[i]);kp[i]++;update(kp[i]);res+=i-Quary(kp[i]);}int minn=res;for(int i=n;i>=2;--i){ res+=2*kp[i]-n-1;//每移动一次增加kp[i]-1个逆序数，同时减少n-kp[i]个逆序数。。。minn=min(minn,res);}printf("%d\n",minn);}return 0;
}
这篇关于http://acm.hdu.edu.cn/showproblem.php?pid=1394的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
