/* 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 ;
}
分享到:
相关推荐
杭州电子科技大学ACM培训课件 来自杭电ACM官方论坛 拿来和大家分享一下 想到有些朋友论坛积分不够 现在特地拿来免费供大家下载 希望对ACM初学者能够有所帮助
一个十分简单的程序,能够ac杭电hdu的第2050题,无注释,简单明了
计算机网络复习大纲_杭电hdu.pdf
计算机网络复习大纲_杭电hdu借鉴.pdf
计算机网络复习大纲_杭电hdu整理.pdf
计算机网络复习大纲_杭电hdu参考.pdf
杭电ACM1005题源代码,AC了的程序,无问题……
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
杭电ACMhdu1163
hdu 1166线段树代码
hdu 1166线段树
杭电hdu acm资料所用杭电的acm题
【hdu5306】Gorgeous Sequence 线段树区间最值操作-附件资源
压缩包包含十份报告,已经通过验收,实验内容:交换机、生成树、静态路由、NAT等完全根据教材实验要求
HDU2000至2099题的题目以及AC代码(含思路) 适合刚刚接触ACM的同学哦~ emmmm凑字
杭电acm培训课件 杭电acm培训课件 杭电acm培训课件 杭电acm培训课件