hdu 1394(树状数组求逆序数)

75 阅读 0 评论 50 点赞

我是靠谱客的博主高大大山，最近开发中收集的这篇文章主要介绍hdu 1394(树状数组求逆序数)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

解题思路：这道题是求循环数组中逆序数最小值，求逆序数这里肯定是用树状数组。只是这里有一点点变化，由于题目中n位数是0-n-1的一个排列，所以num[i]可表示为比num[i]小的数的个数。把第一位的数挪到最后一位，那么整个序列的逆序数变化为ans =ans - num[0] + (n-1-num[0])，num[0]表示后面的n-1位对逆序数的贡献，n-1-num[0]表示把最后一位挪过来对逆序数所作出的贡献。由于最小是为0，所以更新树状数组时多加个1。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn = 5005;
int num[maxn];
int n,tree[maxn<<2];

int lowbit(int x)
{
	return x & -x;
}

void update(int x,int d)
{
	for(int i = x; i <= n; i += lowbit(i))
	{
		tree[i] += d;
	}
}

int getsum(int x)
{
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i))
	{
		sum += tree[i];
	}
	return sum;
}

int main()
{
	while(cin >> n)
	{
		memset(tree,0,sizeof(tree));
		for(int i = 1; i <= n; i++)
		{
			scanf("%d",&num[i]);
		}
		int ans = 0;
		for(int i = 1; i <= n; i++)
		{
			update(num[i]+1,1);
			ans += i - 1 - getsum(num[i]);
		}
		int MIN = ans;
		for(int i = 1; i <= n; i++)
		{
			ans = ans - num[i] + (n - 1 - num[i]);
			MIN = min(MIN,ans);
		}
		cout << MIN << endl;
	}
	return 0;
}