- 浏览: 601254 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ1442题意:
ADD(a)表示向集合中增加元素a,get表示取出第k小元素,k根据get出现的次数不断变化,出现多少次取第几小数。
样例:
Sample Input
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output
3
3
1
2
解释:
输入 n = 7 m =4,然后第一行输入n个数,然后另一行输入m个数
index = 1
1:输出n个数中前1个数中的第Index(1)小值
index=2
2:输出n个数中前2个数中的第index(2)小值
index=3
6:输出n个数中前6个数中的第index(3)小值
index=4
6:输出n个数中前6个数中的第index(4)小值
输入保证m个数单调递增
题解:每次取第k小元素,k不断更新。使用两个堆,来完成。 小顶堆负责,选出最小的元素,大顶堆负责,选出k个元素中最大的元素,即第k小元素
ADD(a)表示向集合中增加元素a,get表示取出第k小元素,k根据get出现的次数不断变化,出现多少次取第几小数。
样例:
Sample Input
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output
3
3
1
2
解释:
输入 n = 7 m =4,然后第一行输入n个数,然后另一行输入m个数
index = 1
1:输出n个数中前1个数中的第Index(1)小值
index=2
2:输出n个数中前2个数中的第index(2)小值
index=3
6:输出n个数中前6个数中的第index(3)小值
index=4
6:输出n个数中前6个数中的第index(4)小值
输入保证m个数单调递增
题解:每次取第k小元素,k不断更新。使用两个堆,来完成。 小顶堆负责,选出最小的元素,大顶堆负责,选出k个元素中最大的元素,即第k小元素
import java.util.Scanner; public class Main{ int tree1[];//大顶堆 int k1; int tree2[];//小顶堆 int k2; int M, N; int A[]; public Main(){ } //tree:大顶堆 void build1(int[] tree, int k) //从下标k开始,大堆向上调整到根 { int p = k; while(p != 1) { if(tree[p] > tree[p / 2]) //如果大于父亲 { int temp = tree[p]; //交换 tree[p] = tree[p / 2]; tree[p / 2] = temp; } p = p / 2; //指向父亲 } } //tree:小顶堆 void build2(int[] tree, int k) //从k开始,小堆向上调整 { int p = k; while(p != 1) { if(tree[p] < tree[p / 2]) //如果小于交亲 { int temp = tree[p]; //交换 tree[p] = tree[p / 2]; tree[p / 2] = temp; } p = p / 2; //指向父亲 } } //tree:大顶堆 void update1(int[] tree, int k){//向下调整大顶堆的根. int p = 1; //指向根 while(2 * p <= k) { int son; if(2 * p == k || tree[2 * p] > tree[2 * p + 1]) son = 2 * p; else son = 2 * p + 1; if(tree[p] < tree[son]) //如果父节点的值小于左右儿子中最大者,交换 { int temp = tree[p]; tree[p] = tree[son]; tree[son] = temp; } p = son; //指向儿子节点 } } //tree:小顶堆 void update2(int[] tree, int k) //向下调整小顶堆的根,直到k { int p = 1; while(2 * p <= k) { int son; if(2 * p == k || tree[2 * p] < tree[2 * p + 1]) //取左右儿子中的较小者 son = 2 * p; else son = 2 * p + 1; if(tree[p] > tree[son]) //如果父节点的值大于左右儿子中最大者,交换 { int temp = tree[p]; tree[p] = tree[son]; tree[son] = temp; } p = son; } } public void go(){ Scanner in=new Scanner(System.in); while(in.hasNext()) { M=in.nextInt(); N=in.nextInt(); A=new int[M+1]; tree1=new int[M+1]; tree2=new int[M+1]; for(int i = 1; i <= M; ++ i) A[i]=in.nextInt();//将M个元素全部读入A int pre = 0; k1 = k2 = 0; for(int i = 1; i <= N; ++ i) //共N轮 { int a=in.nextInt(); for(int j = pre + 1; j <= a; ++ j) //从A中读入前a个元素到tree2 { tree2[++k2] = A[j]; //读一个,调整一个 build2(tree2, k2); //构建tree2使之成为最小堆 } pre = a; tree1[++ k1] = tree2[1]; //将最小堆的堆顶元素放入tree1中 build1(tree1, k1); //构建tree1使之成为最大堆 tree2[1] = tree2[k2 --]; //删除最小堆的堆顶元素,最小堆的最后一个元素放到堆顶 update2(tree2, k2); //调整,使tree2成为小顶堆 while(k2 != 0 && tree1[1] > tree2[1]) { int temp = tree1[1]; tree1[1] = tree2[1]; tree2[1] = temp; update1(tree1, k1); //调整,使tree1成为大顶堆 update2(tree2, k2); //调整,使tree2成为小顶堆 } System.out.printf("%d\n", tree1[1]); } } } public static void main(String args[]){ Main ma=new Main(); ma.go(); } }
- Main111119.zip (1.2 KB)
- 下载次数: 1
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3746题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1654POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3054POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1478POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1929题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1640关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1869关于堆排序请参看:http://128kj.iteye.com ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1894POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1765POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1646分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2248接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1544关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1397接前文:二维树状数组学习之一:彻底理解http://128kj ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1824关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1815关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1817关于树状数组,请参考:http://128kj.iteye.c ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2100POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
线段树练习POJ 3264
2012-12-03 21:16 1343问题:有n只奶牛排成一列,他们有各自的身高Hi,有Q个区间,分 ... -
在POJ中使用StreamTokenizer从命令行获取输入
2012-12-03 12:21 2151在http://poj.org/上用JAVA解题一般用 ... -
二叉搜索树练习 POJ 1577
2012-11-25 20:04 2234一棵二叉查找树是按二叉树结构来组织的。这样的树可以用链表 ...
相关推荐
标题“大顶堆应用:POJ2010”指的是一个关于大顶堆算法在解决实际问题中的应用,特别是针对编程竞赛网站POJ(Programming Online Judge)上的问题2010。大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其...
标题“堆排序练习:POJ 2388”指的是一个关于使用堆排序算法解决编程竞赛问题的实践案例。在编程竞赛中,如POJ(Programming Online Judge)平台上的问题2388,参赛者经常需要高效地解决排序问题,而堆排序作为一种...
【标题】"凸包练习: POJ 2187(JAVA)" 是一个关于编程算法的挑战,主要涉及计算机科学中的几何算法。在本问题中,我们关注的是二维平面上的点集及其凸包(Convex Hull)的概念。凸包可以被理解为一个最小的多边形,该...
【标题】"树状数组练习:POJ 2481(JAVA)" 是一篇关于使用树状数组(也称为线段树)解决编程竞赛问题的文章。这篇文章可能详细讲解了如何运用这种数据结构来解决特定的问题POJ 2481。POJ(Programming Online Judge)...
【标题】"树状数组练习:POJ 3067" 树状数组,也称为线段树(Segment Tree),是一种高效的数据结构,用于处理区间查询和修改问题。在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。...
这个练习题目,"POJ 2388",显然是通过编程实现直接插入排序来解决一个特定的问题。在这个问题中,我们需要理解直接插入排序的机制,并能用Java语言编写出高效的代码。 直接插入排序的基本步骤如下: 1. 从第二个...
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
(4) 哈希表和二分查找等高效查找法:poj3349, poj3274, POJ2151, poj1840, poj2002, poj2503 (5) 哈夫曼树:poj3253 (6) 堆 (7) trie树:poj2513 四、简单搜索 本部分涵盖了简单搜索,包括深度优先搜索、广度优先...
* POJ3109、POJ1478、POJ1462、POJ2729、POJ2048、POJ3336、POJ3315、POJ2148、POJ1263 八、附录 * ACM算法列表 + 哈希表、哈希数组 + 堆、优先队列 + 双端队列可并堆左偏堆 + Treap伸展树并查集 + 集合计数...
例题:poj1860、poj3259、poj1062、poj2253、poj1125、poj2240。 * 最小生成树算法:最小生成树算法是指在图中寻找最小的生成树的算法。例题:poj1789、poj2485、poj1258、poj3026。 * 拓扑排序:拓扑排序是指对有向...
+ poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...
POJ(Peking University Online Judge)是一个知名的在线编程评测平台,提供了大量的编程题目供用户练习。这些题目按照不同的算法和技术进行了分类,以便用户能够有针对性地进行学习和提高。 ### 一、算法: #### ...
标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...
《田忌赛马:POJ 2287 贪心解法解析》 在计算机科学领域,算法是解决问题的核心。"田忌赛马"这个题目来源于古代中国的一个著名故事,而在这个故事的基础上,被引入到了编程竞赛的场景中。POJ(Programming Online ...
- 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
夹角越小,排序位置越靠前。在实际操作中,为了避免角度比较的复杂性,通常会转换为比较向量的叉积,因为两个向量的叉积与它们构成的角度的正弦值成比例。 深度优先搜索在此问题中的应用可能是在构建某种搜索树或者...
- 示例题目:POJ 3349, POJ 3274, POJ 2151, POJ 1840, POJ 2002, POJ 2503 ##### 2. 图算法 - **最短路径**:包括迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)等,适用于求解两点之间的最短...
poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...