首页 > 代码库 > HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)
HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1394
题意:给你一个n个数的序列,其中组成的数只有0-n,我们可以进行这么一种操作:把第一个数移到最后一个,次数不限。问,在原始数列和最新生成的数列中逆序数最小可以是多少?
刚开始以为需要枚举求逆序数,但最后知道了这个题是有规律的:一个由0-n组成的n个数的数列,当第一个数移到最后一位的时候,整个数列的逆序数会减少x[i](移动前,后面比他小的),会增加n-x[i]-1(移动后,前面比他大的)。
那么这个题就成了单纯求原始数列的逆序数。
之前求逆序数用过归并,也用过线段树,可惜没总结,当时的题目还需要离散化。现在先总结这个简单的,等继续回顾暑假内容的时候会遇到的。
线段树求逆序数
因为线段树善于解决区间问题,那么我们可以用它快速区间求和,我们把每个数纳入线段树,当新录入一个数之前,统计已经录入的几个数比他大,以此类推,最后的统计和就是逆序数。
代码:
#include <iostream> #include <cstdio> #include <algorithm> #define LS rt << 1 #define RS rt << 1 | 1 #define LSON l,m,rt << 1 #define RSON m + 1,r,rt << 1 | 1 #define MID (l + r) >> 1 #define MAX 5000 using namespace std; int num[MAX << 2]; int x[MAX + 10]; inline void pushup(int rt) { num[rt] = num[LS] + num[RS]; } void build(int l,int r,int rt) { num[rt] = 0; if(l == r) return ; int m = MID; build(LSON); build(RSON); } void update(int p,int l,int r,int rt) { if(l == r) { num[rt]++; return ; } int m = MID; if(p <= m) update(p,LSON); else update(p,RSON); pushup(rt); } int query(int ql,int qr,int l,int r,int rt) { if(l >= ql && r <= qr) { return num[rt]; } int m = MID; int ret = 0; if(ql <= m) ret += query(ql,qr,LSON); if(qr > m) ret += query(ql,qr,RSON); return ret; } int main() { int n; while(~scanf("%d",&n)) { int sum = 0; build(0,n - 1,1); for(int i = 0;i < n;i++) { scanf("%d",&x[i]); sum += query(x[i],n - 1,0,n - 1,1); update(x[i],0,n - 1,1); } int ans = sum; for(int i = 0;i < n;i++) { //0-n的数,把第一个数移到最后一位后 //整个数列的逆序数会减少x[i](移动前,后面比他小的) //会增加n-x[i]-1(移动后,前面比他大的) sum += n - x[i] - x[i] - 1; ans = min(ans,sum); } printf("%d\n",ans); } return 0; }
HDU 1394 Minimum Inversion Number (线段树 单点更新 求逆序数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。