【樹狀數組】 HDOJ 1394 Minimum Inversion Number

樹狀數組求逆序數問題，每次把最前面的數放到最後面，問最小的逆序數是多少。。注意到題目中數是1-n就比較容易想到解法了，不過如果不是1-n也可以先離散再做。。。先用樹狀數組求一次初始順序的，再依次把目前的逆序減去這個數再減1（也就是這個數後面比他小的數的個數），然後加上n減這個數（就是這個數前面比他大的數的個數）。。。最後加上一個輸入加速，程式直接跑到第一面了~~~

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#define maxn 5001
#define eps 1e-6
#define mod 1000000007
#define INF 99999999
#define lowbit(x) (x&(-x))
#define lson o<<1, L, mid
#define rson o<<1 | 1, mid+1, R
typedef long long LL;
using namespace std;

int tree[maxn];
int num[maxn];
int n, tmp;

void add(int x)
{
	for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=1;
}
int sum(int x)
{
	int ans=0;
	for(int i=x;i>0;i-=lowbit(i)) ans+=tree[i];
	return ans;
}
void work(void)
{
	int i, ans=0;
	memset(tree, 0, sizeof tree);
	for(i=n;i>0;i--){
		ans+=sum(num[i]);
		add(num[i]);
	}
	tmp=ans;
}
int get(void)
{
	int temp=0;
	char ch=getchar();
	while(ch>='0' && ch<='9')
		temp=temp*10+ch-'0', ch=getchar();
	return temp+1;
}
int main(void)
{
	int i, mi;
	while(scanf("%d",&n)!=EOF){
		getchar();
		for(i=1;i<=n;i++) num[i]=get();
		work();
		mi=tmp;
		for(i=1;i<n;i++){
			tmp-=num[i]-1;
			tmp+=n-num[i];
			if(tmp<mi) mi=tmp;
		}
		printf("%d\n",mi);
	}
	return 0;
}