hdu-1394 求逆序数

http://acm.hdu.edu.cn/showproblem.php?pid=1394

首先建立空树，将 a[i] 逐个插入

计算一个序列n排列的最小逆序数

首先用线段树算出出事序列的逆序数，然后找规律推出排列的最小逆序数。

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include <sstream>
#include <time.h>
#include <utility> 
#include <malloc.h> 

using namespace std;

#define Max 5010

int a[5010];
int n;
int ans;
int sum;

struct
{
	int left;
	int right;
	int num;
}b[4 * Max];

void build(int left, int right, int i)//建立空树
{
	b[i].right = right;
	b[i].left = left;
	b[i].num = 0;
	
	if (b[i].left == b[i].right)
		return;

	int mid = (left + right) / 2;
	build(left, mid, i * 2);
	build(mid + 1, right, i * 2 + 1);
}

void update(int value, int i)//更新第value个节点， 从跟节点1开始更新到叶子节点value
{
	if (b[i].left == value && b[i].right == value)
	{
		b[i].num = 1;
		return;
	}
	int mid = (b[i].left + b[i].right) / 2;
	
	if (value <= mid)
		update(value, i * 2);//左子树
	else
		update(value, i * 2 + 1);//右子树

	b[i].num = b[i * 2].num + b[i * 2 + 1].num;//更新根节点
}

int query(int id ,int n,int i)//计算有多少个
{
	if (id <= b[i].left  && b[i].right <= n)
	{
		return b[i].num;
	}
	else
	{
		int mid = (b[i].left + b[i].right)/2;
		int ans1 = 0,ans2 =0;
		if (id <= mid)
		{
			ans1 = query(id, n, i * 2);
		}
		if (mid < n)
		{
			ans2 = query(id, n, i * 2 + 1);
		}
		return ans1 + ans2;
	}
}

int main()
{
	while (scanf("%d",&n)!=EOF)
	{
		build(0,n-1,1);
		ans = 0; sum = 0;

		for (int i = 0; i < n; i++)
		{
			scanf("%d",&a[i]);
			sum += query(a[i]+1,n-1,1);//计算比a[i]大的个数
			update(a[i],1);//更新a[i]
		}

		ans = sum;
		//printf("%d\n", ans);
		for (int i = 0; i < n; i++)
		{
			sum = sum + (n - a[i] -1) - (a[i]);//当把第一个数移到最后一位，
			ans = min(sum, ans);               //比他大的有 n - a[i] + 1 个，比他小的有a[i]个（下标从 0 开始）
		}
		
		printf("%d\n",ans);
	}
	return 0;
}

hdu-1394 求逆序数

原文：http://blog.csdn.net/u014427196/article/details/42213265