- 浏览: 583777 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
设A[1…n]是一个包含n个不同数的数组。如果在i<j的情况下,有A[i]>A[j],则(i,j)就称为A中的一个逆序对(inversion)
现给出一个数列,求该数列中的逆序对数(逆序数)。最直接的暴力方法;
两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,
当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:
int sum = 0;
for(int i = 0; i < size; ++i) {
for(int j = i+1; j < size; ++j){
if(arr[i] > arr[j]){
++sum;
}
}
}
return sum;
下面方法用线段树,逆序数就是一个“区间和”的问题:
对于数列中的每个元素,它对应的逆序数便是之前序列中大于该元素的元素个数和。
由于线段树的插入和查询操作皆可以在lgn的时间内完成,故遍历一个数列求逆序数的时间复杂度为O(nlgn)
例:HDU1394
给你一个数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,
那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!
样例:
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
分析:
线段树节点这样定义:
class Seg_Tree {//线段树节点
int left,right;
int val;//区间内已插入的节点数
int calmid() {
return (left+right)/2;
}
}
先以区间[0,9]为根节点建立val都为0的线段树,
再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间[1,9]已插入的节点数(如果存在,必与1构成逆序) v1=0
在线段树中插入3, 插入之前先询问区间[3,9]已插入的节点数(如果存在,必与3构成逆序) v2=0
在线段树中插入6, 插入之前先询问区间[6,9]已插入的节点数(如果存在,必与6构成逆序) v3=0
在线段树中插入9, 插入之前先询问区间[9,9]已插入的节点数(如果存在,必与9构成逆序) v4=0
在线段树中插入0, 插入之前先询问区间[0,9]已插入的节点数(如果存在,必与0构成逆序) v5=4
在线段树中插入8, 插入之前先询问区间[8,9]已插入的节点数(如果存在,必与8构成逆序) v6=1
在线段树中插入5, 插入之前先询问区间[5,9]已插入的节点数(如果存在,必与5构成逆序) v7=3
在线段树中插入7, 插入之前先询问区间[7,9]已插入的节点数(如果存在,必与7构成逆序) v8=2
在线段树中插入4, 插入之前先询问区间[4,9]已插入的节点数(如果存在,必与4构成逆序) v9=5
在线段树中插入2, 插入之前先询问区间[2,9]已插入的节点数(如果存在,必与2构成逆序) v10=7
累加v1+……+v10 =22,这就是1 3 6 9 0 8 5 7 4 2的逆序数了.
这题要把第一个数放到最后
3 6 9 0 8 5 7 4 2 1
这样就增加了9个逆序,其逆序为22+9=31
6 9 0 8 5 7 4 2 1 3
这样增加了6个,减少了3个,其逆序数为31+6-3=34;
............
//公式:第一个数移到最后位置后逆序数
//sum=sum+(-low[a[i]]+up[a[i]]),low[a[i]]表示比a[i]小的数
//在0-(n-1)序列里low[a[i]]=a[i],up[a[i]]=n-a[i]-1;
最后AC过的代码:
源码:
现给出一个数列,求该数列中的逆序对数(逆序数)。最直接的暴力方法;
两层for循环就可以算出来逆序数:每遇到一个元素回头遍历寻找比其大的元素个数即可,
当然向后寻找比其小的元素个数也可以,复杂度为O(n^2),代码:
int sum = 0;
for(int i = 0; i < size; ++i) {
for(int j = i+1; j < size; ++j){
if(arr[i] > arr[j]){
++sum;
}
}
}
return sum;
下面方法用线段树,逆序数就是一个“区间和”的问题:
对于数列中的每个元素,它对应的逆序数便是之前序列中大于该元素的元素个数和。
由于线段树的插入和查询操作皆可以在lgn的时间内完成,故遍历一个数列求逆序数的时间复杂度为O(nlgn)
例:HDU1394
给你一个数字组成的序列,然后进行这样的操作,每次将最前面一个元素放到最后面去会得到一个序列,
那么这样就形成了n个序列,那么每个序列都有一个逆序数,找出其中最小的一个输出!
样例:
Sample Input
10
1 3 6 9 0 8 5 7 4 2
Sample Output
16
分析:
线段树节点这样定义:
class Seg_Tree {//线段树节点
int left,right;
int val;//区间内已插入的节点数
int calmid() {
return (left+right)/2;
}
}
先以区间[0,9]为根节点建立val都为0的线段树,
再看看怎样求下面序列的逆序数:
1 3 6 9 0 8 5 7 4 2
在线段树中插入1, 插入之前先询问区间[1,9]已插入的节点数(如果存在,必与1构成逆序) v1=0
在线段树中插入3, 插入之前先询问区间[3,9]已插入的节点数(如果存在,必与3构成逆序) v2=0
在线段树中插入6, 插入之前先询问区间[6,9]已插入的节点数(如果存在,必与6构成逆序) v3=0
在线段树中插入9, 插入之前先询问区间[9,9]已插入的节点数(如果存在,必与9构成逆序) v4=0
在线段树中插入0, 插入之前先询问区间[0,9]已插入的节点数(如果存在,必与0构成逆序) v5=4
在线段树中插入8, 插入之前先询问区间[8,9]已插入的节点数(如果存在,必与8构成逆序) v6=1
在线段树中插入5, 插入之前先询问区间[5,9]已插入的节点数(如果存在,必与5构成逆序) v7=3
在线段树中插入7, 插入之前先询问区间[7,9]已插入的节点数(如果存在,必与7构成逆序) v8=2
在线段树中插入4, 插入之前先询问区间[4,9]已插入的节点数(如果存在,必与4构成逆序) v9=5
在线段树中插入2, 插入之前先询问区间[2,9]已插入的节点数(如果存在,必与2构成逆序) v10=7
累加v1+……+v10 =22,这就是1 3 6 9 0 8 5 7 4 2的逆序数了.
这题要把第一个数放到最后
3 6 9 0 8 5 7 4 2 1
这样就增加了9个逆序,其逆序为22+9=31
6 9 0 8 5 7 4 2 1 3
这样增加了6个,减少了3个,其逆序数为31+6-3=34;
............
//公式:第一个数移到最后位置后逆序数
//sum=sum+(-low[a[i]]+up[a[i]]),low[a[i]]表示比a[i]小的数
//在0-(n-1)序列里low[a[i]]=a[i],up[a[i]]=n-a[i]-1;
最后AC过的代码:
import java.util.Scanner; class Seg_Tree {//线段树节点 int left,right; int val;//区间内已插入的节点数 int calmid() { return (left+right)/2; } } public class Main{ private int LL(int x) { return x<<1;} //两倍; private int RR(int x) { return x<<1|1;} //两倍+1; Seg_Tree tt[]; public Main(){ tt=new Seg_Tree[16370];//用数组实现线段树 for(int i=0;i<16370;i++) tt[i]=new Seg_Tree(); } private void build(int left,int right,int idx) {//构建一棵val值全为0的线段树 tt[idx].left = left; tt[idx].right = right; tt[idx].val = 0; if(left == right) return ; int mid = tt[idx].calmid(); build(left,mid,LL(idx)); build(mid+1,right,RR(idx)); } /* 如果将节点全部插入,应该是下面结果: C:\java>java Main 10 1 3 6 9 0 8 5 7 4 2 [0,0]=.val=1 [0,1].val=2 [1,1].val=1 [0,2].val=3 [2,2].val=1 [0,4].val=5 [3,3].val=1 [3,4].val=2 [4,4].val=1 [0,9].val=10 [5,5].val=1 [5,6].val=2 [6,6].val=1 [5,7].val=3 [7,7].val=1 [5,9].val=5 [8,8].val=1 [8,9].val=2 [9,9].val=1 */ private void insert(int aim,int l,int r,int k){ //将aim插入到线段树 if(tt[k].left==aim&&tt[k].right==aim) { tt[k].val++;return ; } if(aim<=tt[k].calmid()) insert(aim,l,tt[k].calmid(),LL(k)); else insert(aim,tt[k].calmid()+1,r,2*k+1); tt[k].val=tt[LL(k)].val+tt[RR(k)].val; } public void printTree(int i){//中序遍历线段树 if(2*i>16370) return; printTree(2*i); if(tt[i].right!=0) System.out.print("["+tt[i].left+","+tt[i].right+"]"+".val="+tt[i].val+" ");//注意,没有输出[0,0] printTree(2*i+1); } //查询[left,right]中已插入的节点数 private int query(int left,int right,int idx){ if(left == tt[idx].left && right == tt[idx].right) return tt[idx].val; int mid = tt[idx].calmid(); if(right <= mid){ return query(left,right,LL(idx)); } else if(mid < left) { return query(left,right,RR(idx)); } else { return query(left,mid,LL(idx)) + query(mid+1,right,RR(idx)); } } public static void main(String[] args){ Scanner in=new Scanner(System.in); int n; while(in.hasNext()) { n=in.nextInt(); Main ma=new Main(); int val[]=new int[n]; ma.build(0,n-1,1); int sum = 0; for(int i=0;i<n;i++){ val[i]=in.nextInt(); sum += ma.query(val[i],n-1,1);//先查询 ma.insert(val[i],0,n-1,1);//后插入 } // ma.printTree(1); // System.out.println();//中序遍历线段树 // System.out.println(sum); int ret = sum; for(int i=0;i<n;i++){ sum = sum - val[i] + (n - val[i] - 1); ret=Math.min(ret,sum); } System.out.println(ret); } } }
源码:
- MainHDU1394.zip (1.3 KB)
- 下载次数: 0
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2326北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1945import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1353接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2417当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1672关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1746关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1699一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2021POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2031继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2497继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2600先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2215一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2009形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2785例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2060字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18568堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 3985一、什么是并查集 ... -
根据二叉树前序遍历和中序遍历的结果输出后序遍历(java)
2012-10-07 19:58 3271前序遍历的第一个元素为根节点,在中序遍历中找到这个根节点 ...
相关推荐
利用归并排序求逆序数,复杂度在O(nlgn)含测试用例
求逆序数的方法很多。最容易想到的办法是分别对序列中每一个元素求其逆序数,再求所有元素的逆序数总和,易分析得出这样的方法其时间复杂度为O(n2)。而这里采用的分治法求逆序数,其时间复杂度为O(nlogn)。
归并排序求逆序数
利用归并排序实现关于逆序数的计算,Java程序
算法导论 课上的 用mergesort求逆序数对的matlab源码,想挣点分,所以就不免费下载了~~~~ 见谅
字符串逆序字符串逆序代码 java python node 等语言代码源码.doc字符串逆序代码 java python node 等语言代码源码.doc字符串逆序代码 java python node 等语言代码源码.doc字符串逆序代码 java python node 等语言...
逆序数c++源码,直接运行
利用归并排序求逆序对,有分治和递归,不过没有主函数
求逆序数对1
java 利用栈将字符串逆序输出 java 利用栈将字符串逆序输出 java 利用栈将字符串逆序输出
该资源提供了一份全面的指南,介绍了如何在Java中实现数字逆序。文档中涵盖了数字逆序的基本概念,包括如何从数字中提取数字,以及如何颠倒数字的顺序。此外,文档还包括一个逐步指南,介绍如何在Java中实现逆序数字...
求输入数据后求逆序数问题。常用于本科,研究生的算法作业。里面是工程文件,可以直接使用。
有一实数序列a1,a2,....an,若i且ai>aj,则(ai,aj)形成了一个逆序对,请使用分治算法求整个序列中逆序对个数,并分析算法时间复杂度。
求逆序数的通用算法.cpp
算法-求逆序对(信息学奥赛一本通-T1311).rar
信息学奥赛一本通1311:求逆序数对
NlogN求逆序数对#include<iostream>#include<stdio.h>#include<string.h>#include<algorith
逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出数字.cpp逆序输出...
利用二路归并排序求逆序对,很巧妙的一种算法