首页 > 其他 > 详细

HDU 1394 Minimum Inversion Number (最小逆序对数&RMQ线段树)

时间:2014-02-19 13:38:52      阅读:343      评论:0      收藏:0      [点我收藏+]

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


每读一个数,先查询前面有多少比它大的数(在代码中我们是查询[x,n-1]范围内的数),然后将位置x的数+1

把第一个数在序列末尾时,因为比x小的数(0~x-1)都在x前面了,所以逆序对数减少了x;因为比x大的数(x+1~n-1)都在x前面了,所以逆序对数增加了n-1-x。这样每次移动,逆序对数 += n-1-2*x


完整代码:

/*78ms,320KB*/

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define root 0, n, 1
const int mx = 5000;

int sum[mx << 2], x[mx];

inline void pushup(int rt)
{
	sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}

void update(int p, int addval, int l, int r, int rt)
{
	if (l == r)
	{
		sum[rt] += addval;
		return;
	}
	int m = (l + r) >> 1;
	if (p <= m) update(p, addval, lson);
	else update(p, addval, rson);
	pushup(rt);
}

int query(int ql, int qr, int l, int r, int rt)
{
	if (ql <= l && r <= qr)
	{
		return sum[rt];
	}
	int sum = 0, m = (l + r) >> 1;
	if (ql <= m) sum += query(ql, qr, lson);
	if (m < qr) sum += query(ql, qr, rson);
	return sum;
}

int main()
{
	int n, i, inver, minans;
	while (~scanf("%d", &n))
	{
		memset(sum, 0, sizeof(sum));
		--n;
		inver = 0;
		for (i = 0; i <= n; ++i)
		{
			scanf("%d", &x[i]);
			inver += query(x[i], n, root);
			update(x[i], 1, root);
			x[i] <<= 1;
		}
		minans = inver;
		for (i = 0; i <= n; ++i)
		{
			inver += n - x[i];
			minans = min(minans, inver);
		}
		printf("%d\n", minans);
	}
	return 0;
}

HDU 1394 Minimum Inversion Number (最小逆序对数&RMQ线段树)

原文:http://blog.csdn.net/synapse7/article/details/19411963

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!