`

杭电 hdu 1394 Minimum Inversion Number 【线段树 + 详细注释 + 有难度】

阅读更多
/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
    Copyright (c) 2011 panyanyany All rights reserved.

    URL   : http://acm.hdu.edu.cn/showproblem.php?pid=1394
    Name  : 1394 Minimum Inversion Number

    Date  : Saturday, September 17, 2011
    Time Stage : 4 hours

    Result: 
4618941	2011-09-17 18:27:45	Accepted	1394
62MS	280K	2745 B
C++	pyy

4618908	2011-09-17 18:22:09	Accepted	1394
62MS	280K	2707 B
C++	pyy

4618903	2011-09-17 18:21:09	Compilation Error
1394
0MS	0K	1662 B
C++	pyy


Test Data :

Review :
呃,线段树,难度还是蛮大的。一看就不会做,然后看解题报告,
一开始看不明白,人家的都没注释,真是很纠结啊,后来终于明白
了什么是“逆序数”以及下面所述的特性,然后线段树的部分就只有
自己想了……

希望大家以后写代码也能多加点注释,即能锻炼自己的书写能力,理
清思路,又能帮助后进的学生,同时将此美德于万万人类中传承下去,
何乐而不为呢……
//----------------------------------------------------------------------------*/

#include <stdio.h>
#include <string.h>

int max (int lhs, int rhs)
{
	return (lhs > rhs ? lhs : rhs) ;
}

int min (int lhs, int rhs)
{
	return lhs < rhs ? lhs : rhs ;
}

typedef struct {
	int left, right ;
	int sum ;
} NODE ;

#define MAXSIZE 5001

int n ;
int a[MAXSIZE] ;
NODE segTree[MAXSIZE * 2] ;

// 构造线段树
void build (int id, int left, int right)
{
	segTree[id].left	= left ;
	segTree[id].right	= right ;
	segTree[id].sum = 0 ;

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

int query (int id, int left, int right)
{
	// 当前节点所代表的区间与要查找的区间 (left, right) 没有交集
	if (segTree[id].left > right || segTree[id].right < left)
		return 0 ;
	// 当前节点所代表的区间在要查找的区间之内
	if (left == segTree[id].left && segTree[id].right == right)
		return segTree[id].sum ;

	int mid = (segTree[id].left + segTree[id].right) / 2 ;
	int sum = 0 ;

	if (right < mid)			// 若待查区间在当前区间的左半边
		sum += query (id * 2, left, right) ;
	// 若待查区间在当前区间的右半边, 可能是 hdu 数据不严谨,
	// 下面判断中换成 mid < left 也能过……
	else if (mid + 1 < left)
		sum += query (id * 2 + 1, left, right) ;
	else						// 若待查区间 横跨 当前区间的中部
		sum += query (id * 2, left, mid) + query (id * 2 + 1, mid + 1, right) ;

	return sum ;
}

int update (int id, int val)
{
	// 找到叶子
	if (segTree[id].left == val && segTree[id].right == val)
	{
		return segTree[id].sum = 1 ;
	}

	// val 不在当前节点所代表的范围内
	if (segTree[id].left > val || segTree[id].right < val)
		return 0 ;

	int mid = (segTree[id].left + segTree[id].right) / 2 ;

	// val 分布在当前区间的右半边
	if (mid < val)	// 不能等于
		segTree[id].sum += update (id * 2 + 1, val) ;
	// val 分布在当前区间的左半边
	else
		segTree[id].sum += update (id * 2, val) ;

	return 1 ;
}

int main ()
{
	int i, j ;
	int sum, res ;
	while (scanf ("%d", &n) != EOF)
	{
		// 构造线段树
		build (1, 1, n) ;
		sum = 0 ;
		for (i = 0 ; i < n ; ++i)
		{
			scanf ("%d", &a[i]) ;
			// 查询比 a[i] 大的数是否出现过,返回出现的次数,
			// 即为 满足 x > a[i] 的逆序数对
			sum += query (1, a[i] + 1, n - 1) ;
			// 查询完之后,将 a[i] 加入线段树中
			update (1, a[i]) ;
		}

		// 首先要知道这么个性质:对任意的一列逆序数,设其第一个数为 a 
		// 则在 a 之后比 a 小的数必然有 a 个:0, 1, 2, ... , a - 1
		res = sum ;
		for (i = 0 ; i < n ; ++i)
		{
			sum = sum - a[i] + (n - a[i] - 1) ;
			res = min (res, sum) ;
		}
		printf ("%d\n", res) ;
	}
	return 0 ;
}


1
1
分享到:
评论
1 楼 基德KID.1412 2012-02-10  
y神写得如此的美啊,太特么好勒!特此顶上! ----KIDx

相关推荐

    杭电HDU ACM培训课件

    《杭电HDU ACM培训课件》是一份珍贵的学习资源,源自杭州电子科技大学的ACM竞赛培训课程。这些课件是官方论坛上分享的,旨在为那些积分不足无法获取资源或者对ACM编程竞赛感兴趣的初学者提供帮助。下面将详细阐述这...

    ACM hdu 线段树题目+源代码

    ACM hdu 线段树题目+源代码 线段树是一种非常重要的数据结构,它广泛应用于算法竞赛和实际编程中。今天,我们将通过 ACM hdu 的几个题目来学习和掌握线段树的基本概念和应用。 线段树的基本概念 线段树是一种...

    杭电HDU2050题的ac程序

    一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了

    计算机网络复习大纲_杭电hdu.pdf

    计算机网络复习大纲_杭电hdu.pdf

    线段树完整版

    **案例3:hdu1394 Minimum Inversion Number** - **题意**: 给定一个序列,求最少需要多少次逆序操作使得该序列变为非递减序列。 - **解决思路**: 使用线段树来维护区间内的逆序对数量,通过动态规划的方法来求解...

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu整理.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    计算机网络复习大纲_杭电hdu参考.pdf

    杭电HDU ACM 1005

    杭电ACM1005题源代码,AC了的程序,无问题……

    hdu acm1166线段树

    hdu 1166线段树代码

    hdu 1166线段树

    标题与描述均提到了“hdu 1166线段树”,这表明文章的核心是关于线段树在解决特定问题中的应用。线段树是一种数据结构,主要用于处理区间查询和更新操作,尤其是在大规模数据集上。在本例中,通过分析给定的部分代码...

    杭电操作系统实验 HDU操作系统实验.zip

    杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU操作系统实验.zip杭电操作系统实验 HDU...

    杭电ACMhdu1163

    【标题】:杭电ACMhdu1163 【描述】:这是一道源自杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的ACM编程竞赛题目,编号为1163。这类问题通常需要参赛者利用计算机编程解决数学、逻辑或算法上的挑战,...

    hdu_ACM.rar_ACM_hdu_hdu acm_hdu_ACM_杭电ACM

    杭电hdu acm资料所用杭电的acm题

    HDU杭电 计算机网络实验报告

    这份"HDU杭电 计算机网络实验报告"压缩包提供了丰富的实验材料,涵盖了多个关键的网络技术,包括交换机配置、路由协议、地址转换(NAT)、访问控制列表(ACL)以及动态主机配置协议(DHCP)等。以下是这些实验报告所...

    计算机网络复习大纲_杭电hdu借鉴.pdf

    每一层都有其特定的任务,例如物理层负责数据的物理传输,数据链路层处理相邻节点间的通信,网络层处理网络间的路由选择,运输层确保数据的可靠传输,而应用层则是用户直接交互的接口。 带宽是衡量网络传输能力的...

    线段树入门学习(兼解HDU1754)

    这篇博客“线段树入门学习(兼解HDU1754)”旨在帮助初学者理解线段树的基本概念,并通过解决HDU1754题目来实践其应用。 线段树的核心思想是将一个区间分解成多个子区间,然后对每个子区间进行预处理,存储区间的信息...

    hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj

    【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...

Global site tag (gtag.js) - Google Analytics