首页 > 代码库 > hdoj 1394 Minimum Inversion Number 【线段数】

hdoj 1394 Minimum Inversion Number 【线段数】

题目大意:求移动数列中的第一个元素到最后一位时的最少逆序数。(进行n次移动,求移动过程中最少的逆序数)

难点:

一:什么是逆序数? 定义: 在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。逆序数为偶数的排列称为偶排列;逆序数为奇数的排列称为奇排列。如2431中,21,43,41,31是逆序,逆序数是4,为偶排列。

二:怎么求?

此题分析一下有个技巧对于这道题因为是0~n-1所以我们可以通过下标就可以判别大小,假设此时数列第一个元素为a, 那么当a移动到最后一位的时候,比他小的数(有a个)的逆序数都要减一,比他大的(有n-1-a)都要加一,此时总的逆序数增加了n-1-a-a个;

 我想到有两种思路:1》普通的搜索, 但测试数据5000,太大,而且每次查找逆序数的个数后,都要往后移一位,TL,可能性很大。放弃了这一种思路。

2》线段树,只需要找出来初始数组的逆序数,就可以递推其他的数列的逆序数了(根据上面的技巧);

AC by SWS

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1394

代码:

#include<stdio.h>
#include<string.h>
#define MAXN 5005
#define LC l, m, rt<<1
#define RC m+1, r, rt<<1|1
int sum[MAXN<<2];
int s[MAXN];
void creat(int l, int r, int rt)  //创建线段树,但因为初始全为0, 可以不用这样,直接一个memset就可以了
{
	if(l ==r){
		sum[rt] = 0;
		return;
	}
	int m = (l+r)>>1;
	creat(LC);
	creat(RC);
	sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
void update(int p, int l, int r, int rt)
{
	if(l == r){
		sum[rt]++; //标记等于此位置的序号的数已更新
		return;
	}
	int m = (l+r)>>1;
	if(p<=m) update(p, LC);
	else update(p, RC);
	sum[rt] = sum[rt<<1]+sum[rt<<1|1];
}
int query(int le, int ri, int l, int r, int rt)
{
	if(le <= l&&r<= ri)
	return sum[rt];
	int res = 0;
	int m = (l+r)>>1;
	if(le <= m) res+=query(le, ri, LC);
	if(ri > m) res+= query(le, ri, RC);
	return res;
}
int main()
{
	int n;
	while(scanf("%d", &n) == 1){
		//memset(sum, 0, sizeof(sum));
		creat(0, n-1, 1);
		int sum = 0; //统计初始数列的逆序数
		for(int i = 0; i < n; i ++){
			scanf("%d", &s[i]);
			sum += query(s[i], n-1, 0, n-1, 1);  //关于这个为什么是s[i], n-1, 是因为要判断比s[i]大的数是不是已经更新到了线段树之中,返回此时的相对于s[i]的逆序数)
			update(s[i], 0, n-1, 1);
		}
		int ans  = sum;
		for(int i = 0; i < n; i ++){ //每移动一位总数增加<span style="color: rgb(51, 51, 51); font-family: arial, 宋体, sans-serif; font-size: 14px; line-height: 24px; text-indent: 28px; ">n-1-a-a</span>
			sum += n-s[i]-1-s[i];
			ans = ans< sum?ans:sum; 判断是否为最小
		}
		printf("%d\n", ans);
	}
	return 0;
}