- 浏览: 582960 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分别求出这些区间中最高和最矮的差值。
Sample Input
6 3 (六只奶牛,下面分别是它们的身高,3个区间)
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Sample Input
6 3 (六只奶牛,下面分别是它们的身高,3个区间)
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
import java.io.StreamTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.io.OutputStreamWriter; import java.io.IOException; class tree{ //线段树节点 int left,right,maxvalue,minvalue; } public class Main{ tree[] tt;//线段树,用数组实现 int height[];//奶牛身高 public Main(int[] height){ this.height=height; tt=new tree[131070]; for(int i=0;i<131070;i++) //数组大小的计算参看:http://128kj.iteye.com/blog/1739064 tt[i]=new tree(); } private void built_tree(int lp,int rp,int pos){ //构建以pos为根的线段树 tt[pos].left=lp; tt[pos].right=rp; if(lp==rp){ tt[pos].maxvalue=height[rp]; tt[pos].minvalue=height[lp]; return ; } int mid=(tt[pos].left+tt[pos].right)>>1; built_tree(lp,mid,pos<<1); built_tree(mid+1,rp,pos<<1|1); tt[pos].maxvalue=Math.max(tt[pos<<1].maxvalue,tt[pos<<1|1].maxvalue); tt[pos].minvalue=Math.min(tt[pos<<1].minvalue,tt[pos<<1|1].minvalue); } //找[lp,rp]上的最大值 private int findmax(int lp,int rp,int pos){ if(tt[pos].left==lp&&tt[pos].right==rp){ return tt[pos].maxvalue; } int mid=(tt[pos].left+tt[pos].right)>>1; if(rp<=mid){ return findmax(lp,rp,pos<<1); } else if(lp>mid) return findmax(lp,rp,pos<<1|1); else{ return Math.max( findmax(lp,mid,pos<<1), findmax(mid+1,rp,pos<<1|1)); } } //找[lp,rp]上的最小值 private int findmin(int lp,int rp,int pos){ if(tt[pos].left==lp&&tt[pos].right==rp){ return tt[pos].minvalue; } int mid=(tt[pos].left+tt[pos].right)>>1; if(rp<=mid) return findmin(lp,rp,pos<<1); else if(lp>mid) return findmin(lp,rp,pos<<1|1); else return Math.min( findmin( lp,mid,pos<<1 ),findmin( mid+1,rp,pos<<1|1 ) ); } public static void main(String args[]) throws IOException{ StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); while(st.nextToken() != StreamTokenizer.TT_EOF) { int n=(int) st.nval; st.nextToken(); int q=(int) st.nval; int[] height=new int[n+1]; for(int i=1;i<=n;++i){ st.nextToken(); height[i]=(int) st.nval; } Main ma=new Main(height); ma.built_tree(1,n,1); int x,y; while(q-->0){ st.nextToken(); x=(int) st.nval; st.nextToken(); y=(int) st.nval; int mmax=ma.findmax(x,y,1); int mmin=ma.findmin(x,y,1); System.out.printf("%d\n",mmax-mmin); } out.flush(); } } }
- Main3264.rar (952 Bytes)
- 下载次数: 2
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3655题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1522POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2978POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1429POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1843题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1592关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1819关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1804POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1829POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1723POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1561分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2172接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1496关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1351接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1765关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1663关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1745关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2019POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2097在http://poj.org/上用JAVA解题一般用 ... -
二叉搜索树练习 POJ 1577
2012-11-25 20:04 2116一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1733777
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
poj2823,使用线段树进行查询区域间最大最小值,线段树初步
NULL 博文链接:https://128kj.iteye.com/blog/1746750
这是一道很不错的题目,即可以用线段树做也可以用树状数组,可谓经典。不过当然了线段树是比较难搞,而树状数组是极其简洁的,构造很简单,下面就分别来介绍一下两种方法...
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
NULL 博文链接:https://128kj.iteye.com/blog/1739064
NULL 博文链接:https://128kj.iteye.com/blog/1739733
线段树、树状数组算法入门 加 poj解题报告 pdf文档
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
poj 2763 程序 线段树 LCA 2000MS AC
NULL 博文链接:https://128kj.iteye.com/blog/1745671
大量线段树题目 zoj 1610 线段覆盖 poj 2777 线段覆盖 poj 2528 需要离散化,建树不同,需要处理不同->注意这组数据 3 1 10 1 3 6 10 the ans is 3. hdu 1754 求区间最大值 hdu 1166 求区间和 hdu 1698 成段更新 ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
POJ题解 个人写法 线段树每个人都不一样
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1747400
NULL 博文链接:https://128kj.iteye.com/blog/1754177
大家都用树状数组,但是有人只会用线段树呢? 而且我可以轻易改出一道不能用树状数组的题 在线段树一次次TLE后,有一个ID发帖抱怨 “下次写一个汇编版非递归线段树,再超时?” 可是大家都知道,超时的代码已经2k了...