- 浏览: 603989 次
- 来自: ...
文章分类
最新评论
-
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 3775题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1677POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3062POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1485POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1935题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1645关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1876关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1893POJ1442题意: ADD(a)表示向集合中增加元素a ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1911POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1770POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1663分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2265接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1550关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1844关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1822关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2121POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2158在http://poj.org/上用JAVA解题一般用 ... -
二叉搜索树练习 POJ 1577
2012-11-25 20:04 2256一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表 ...
相关推荐
在本篇中,我们将深入学习二维树状数组的应用,并通过解决POJ 1195问题来实践这一概念。 POJ 1195题目要求我们计算一个二维矩阵中的子矩阵之和。这正是二维树状数组的优势所在,因为我们可以快速地对矩阵的任意矩形...
标题中的“图的深搜+树状数组练习 POJ 3321(JAVA)”指的是一个编程题目,其中涉及到图的深度优先搜索(DFS, Depth First Search)算法和树状数组(也称为线段树,Segment Tree)的数据结构。这个题目来源于POJ...
它扩展了一维树状数组(也称作线段树),能够处理二维或多维的数组更新和查询操作。在POJ 2029这个题目中,我们可能面临的问题是需要对一个二维矩阵进行动态更新和求和查询,例如计算某一个矩形区域内的元素总和。 ...
ACM常用算法及其相应的练习题 ... + poj3264, poj3368 * 并查集的高级应用 + poj1703, poj2492 * KMP算法 + poj1961, poj2406 四、搜索 * 最优化剪枝和可行性剪枝 * 搜索的技巧和优化 + poj3411, poj1724
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
poj2528、poj2777等是线段树的题目,poj2482、poj2352等涉及平衡树,poj1195、poj3321则训练了树状数组。 5. **搜索算法的优化**:poj1699、poj3411等训练搜索技巧和剪枝方法,poj3373、poj1691则介绍了记忆化搜索。...
在初级阶段的基础上,中级阶段涵盖了更多复杂的数据结构和算法,如差分约束系统、最小费用最大流、双连通分量、强连通分支、最小割模型等,以及线段树、树状数组、RMQ查询等高级数据结构的应用。这些内容进一步深化...
树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。 POJ 3067题目大致是这样的:给定一...
- 推荐题目:[poj3264](https://vjudge.net/problem/POJ-3264)、[poj3368](https://vjudge.net/problem/POJ-3368) - 区间查询问题通常涉及线段树或树状数组等数据结构。 5. **字符串匹配** - 推荐题目:[poj1961...
第十一类是线段树,涵盖了至少两个题目,包括 2352 和 2528 等题目。 第十二类是计算几何,涵盖了至少两个题目,包括 1113 和 1922 等题目。 第十三类是高精度,涵盖了至少三个题目,包括 1001 和 1413 等题目。 ...
- **2352** 和 **2528** 两题适合了解线段树的基本应用,虽然没有最少题数要求,但练习线段树对于提高算法能力非常有帮助。 ### 第十二类:计算几何 #### 重要性: 计算几何在图形处理、地图绘制等领域有着广泛的...
- 高级数据结构:平衡树(AVL树、红黑树)、线段树、树状数组、并查集等。 - 特殊的数据结构:后缀数组、LCP数组等用于文本处理的高效结构。 #### 6. 几何题 几何题通常涉及到几何图形的性质、计算等。 - **知识点*...
2. **叉积和点积**:用于判断线段相交、计算距离等,如POJ2031和1039。 3. **多边形算法**:处理多边形的面积计算和相关判定,如点在多边形内、多边形是否相交,如POJ1408和1584。 4. **凸包**:找到图形的最小包围...
对于中级阶段,深入学习 C++ 标准模板库的应用、更复杂的模拟题、差分约束系统、最小费用最大流、双连通分量等复杂图算法、线段树、静态二叉检索树、RMQ 和 KMP 算法等,都是进一步提升算法能力的关键。 总的来说,...
7. **计算几何**:线段树、凸包、最近点对等问题,涉及到二维空间中的几何形状和性质。 8. **数据结构**:栈、队列、链表、树(二叉树、平衡树如AVL、红黑树等)、堆(最大堆、最小堆)、哈希表等,是解决问题的...
POJ是一个在线平台,提供了大量编程题目供参赛者练习,而这个压缩包中的源代码就是对这些问题的解答。 【描述】: "POJ经典268题的源码及分类,ACMer必备,数据结构、算法课程的绝好练习" 这个压缩包不仅包含源代码...
4. 数据结构高级应用:线段树、静态二叉检索树、树状数组、RMQ和并查集的更复杂用法。 5. 搜索优化:最优化剪枝、搜索技巧和记忆化搜索。 这些内容构成了一个全面的ACM训练框架,旨在全面提升参赛者的编程思维、...
- **线段树与树状数组**:适用于解决区间更新与查询问题。 - 示例题目:POJ 2528, POJ 2828, POJ 2777, POJ 2886, POJ 2750 - **二分法**:在特定区间内进行搜索,适用于求解数值优化问题。 - 示例题目:POJ 2031,...
1. **高级数据结构**(如poj2528, poj2828, poj2777, poj2886, poj2750):包括线段树、树状数组、Trie树等,用于解决复杂的数据查询和更新问题。 2. **平衡树**(如poj2482, poj2352):如AVL树、红黑树等,保持树...