- 浏览: 599966 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
POJ2010题意:
奶牛学校招生,c头奶牛报名,要选n头(n为奇数),学校是义务制,所以每头奶牛的学费都由学校负责。每头奶牛都由自己的考试分数和它需要花的学费,学校总共有f的资金,问合法招生方案中中间分数(即排名第(n+1)/2)最高的是多少。
题解:先将所有的奶牛按照分数由低到高排序,假设k是招的奶牛中排名中间的那头,按照排序可知,[1,k-1]中的奶牛必定被招了(n-1)/2头,[k+1,c]中也必定被招了(n-1)/2头,而且无论招的是谁,分数是怎么样,最后影响结果的都只是k的分数。于是,可以预处理low[i]代表[1,i]头牛中选出(n-1)/2头牛的最小花费,high[i]代表[i,c]头牛中选出(n-1)/2头牛的花费,预处理方法可以用一个大顶堆,复杂度nlogn,最后枚举中间牛复杂度n。
【输入】
第一行n、c、f
接下来c行每行两个数字,分别为分数和学费
【输出】
合法招生方案中中位数分数(即排名第(n+1)/2)最高的是多少。
样例:
Sample Input
3 5 70
30 25
50 21
20 20
5 18
35 30
Sample Output
35
AC源码:
奶牛学校招生,c头奶牛报名,要选n头(n为奇数),学校是义务制,所以每头奶牛的学费都由学校负责。每头奶牛都由自己的考试分数和它需要花的学费,学校总共有f的资金,问合法招生方案中中间分数(即排名第(n+1)/2)最高的是多少。
题解:先将所有的奶牛按照分数由低到高排序,假设k是招的奶牛中排名中间的那头,按照排序可知,[1,k-1]中的奶牛必定被招了(n-1)/2头,[k+1,c]中也必定被招了(n-1)/2头,而且无论招的是谁,分数是怎么样,最后影响结果的都只是k的分数。于是,可以预处理low[i]代表[1,i]头牛中选出(n-1)/2头牛的最小花费,high[i]代表[i,c]头牛中选出(n-1)/2头牛的花费,预处理方法可以用一个大顶堆,复杂度nlogn,最后枚举中间牛复杂度n。
【输入】
第一行n、c、f
接下来c行每行两个数字,分别为分数和学费
【输出】
合法招生方案中中位数分数(即排名第(n+1)/2)最高的是多少。
样例:
Sample Input
3 5 70
30 25
50 21
20 20
5 18
35 30
Sample Output
35
AC源码:
import java.util.*; class node implements Comparable { int score, need; public int compareTo(Object o) {//按score升序排列 node b=(node)o; return this.score-b.score; } } public class Main{ node[] p; //所有牛的数组 int n, c, f;//题目中给出的三个条件 int[] h;//维护学费的堆 int r;//堆底的索引 int sum; //记录堆内元素之和 int[] high, low; void up(int i){//向上调整 int j; while(i > 1){ j = i / 2;//i的父亲 if(h[i] > h[j]) swap(i, j); else break; i = j; } } void down(int i){ //向下调整 int j; while(i * 2 <= r){ j = i * 2; //i的左儿子 if(j + 1 <= r && h[j + 1] > h[j]) j++; if(h[j] > h[i]) swap(i, j); else break; i = j; } } void del(int x){ //删除堆顶,将x作为堆顶 sum = sum + x - h[1]; h[1] = x; down(1); } void insert(int x){//在堆底插入 h[++r] = x; sum += x; up(r); } //交换 private void swap(int i, int j) { int temp = h[i]; h[i] = h[j]; h[j] = temp; } public void print(){ for(int i=1;i<=c;i++){ System.out.print("["+p[i].score+","+p[i].need+"] "); } } public static void main(String args[]){ Main ma=new Main(); ma.go(); } public void go(){ Scanner in=new Scanner(System.in); n =in.nextInt(); //n是奇数 c=in.nextInt(); f=in.nextInt(); low=new int[c+1]; high=new int[c+1]; h=new int[c+1]; p=new node[c+1]; for(int i = 1; i <= c; i++){ p[i]=new node(); p[i].score=in.nextInt(); p[i].need=in.nextInt(); } r = sum = 0; Arrays.sort(p, 1, c+1); //按分数升序 n /= 2; for(int i = 1; i <= n; i++) insert(p[i].need); //从开头往后算n/2个牛的学费 low[n] = sum; //记录前面n/2个学费之和 for(int i = n + 1; i <= c - n; i++) { if(p[i].need < h[1]) del(p[i].need); //p[i]的学费比堆顶小,进堆并删除原堆顶 low[i] = sum; //记录前i个牛中取n/2个时的最小学费和 } h=new int[c+1]; r = sum = 0; for(int i = c; i > c - n; i--) insert(p[i].need); //从后面往前算n/2个牛 high[c - n + 1] = sum; //记录最小学费和 for(int i = c - n; i > n; i--) { if(p[i].need < h[1]) del(p[i].need); //p[i]的学费比堆顶小,进堆并删除原堆顶 high[i] = sum; //记录从i开始后面的所有牛中取n/2个时的最小学费和 } int ans = -1; for(int i = c - n; i > n; i--) //枚举中位数,选分数最大的,注意:已经按分数升序排了. if(low[i - 1] + high[i + 1] + p[i].need <= f) { ans = p[i].score; break; } System.out.println(ans); } }
- 11132845_AC_3422MS_8416K.zip (1.4 KB)
- 下载次数: 1
发表评论
-
求推箱子的最小步数(java)
2014-05-06 08:32 3740题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1641POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2389北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1984import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 3050POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1476POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1925题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1639关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1866关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1872POJ1442题意: ADD(a)表示向集合中增加元素a ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1761POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1640分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2242接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1541关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1395接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2465当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1818关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1803关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1816关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1769一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
标题 "大(小)顶堆练习:POJ 1442" 提示我们这是一个关于数据结构和算法的练习题目,特别关注大顶堆或小顶堆的应用。在计算机科学中,大顶堆和小顶堆是两种特殊的二叉堆,它们分别保证了根节点是其子树中最大或最小...
标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...
* 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、...
堆排序是一种基于比较的排序算法,它的核心思想是构建和维护一个大顶堆或小顶堆。大顶堆中,每个父节点的值都大于或等于其子节点;小顶堆则相反。通过不断调整堆,将最大元素(大顶堆)或最小元素(小顶堆)移动到堆...
总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...
(1) C++的标准模版库的应用:poj3096, poj3007 (2) 较为复杂的模拟题的训练:poj3393, poj1472, poj3371, poj1027, poj2706 (3) 差分约束系统的建立和求解:poj1201, poj2983 (4) 最小费用最大流:poj2516, poj2516,...
【描述】虽然描述部分为空,但我们可以推测,作者在博客中可能详细解释了树状数组的概念、特性以及其在解决实际问题中的应用。通常,这样的文章会包含以下几个方面: 1. **树状数组定义**:树状数组是一种高效的...
- 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...
POJ(Programming Online Judge)是国内外广受欢迎的在线编程评测系统,其中的2287题正是以"田忌赛马"为背景的算法问题,主要考察选手对贪心策略的理解和应用。 贪心算法是一种在每一步选择中都采取当前状态下最好...
在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。 POJ 3067题目大致是这样的:给定一个数组,我们需要在数组上进行一系列的查询和修改操作。查询操作询问区间内元素之和,而修改操作...
- **解释**:这一类问题通常涉及基本的数学运算和数学定理的应用。 #### 2. 几何问题 - **例题**:poj1328, poj2109, poj2586 - **解释**:这类题目涉及到几何图形的处理,比如点、线、面等的计算与判断。 #### 3....
* C++的标准模版库的应用:例如 poj3096、poj3007。 * 较为复杂的模拟题的训练:例如 poj3393、poj1472、poj3371、poj1027、poj2706。 2. 图算法: * 差分约束系统的建立和求解:例如 poj1201、poj2983。 * ...
- 为了优化性能,可以考虑使用二分查找法找到待插入元素的正确位置,但这通常只在数组部分有序或元素数量较大时才有效。 - 在实际编程中,通常会使用一个循环来遍历数组的剩余部分,进行插入操作。对于POJ 2388这个...
+ poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...
* C++的标准模版库的应用:C++的标准模版库是指C++语言的标准库,提供了许多有用的算法和数据结构。例题:poj3096、poj3007。 * 较为复杂的模拟题的训练:较为复杂的模拟题是指需要使用多种算法和数据结构来解决的...
标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...
在POJ 1696这个编程题目中,很可能需要解决与极角排序相关的问题。POJ(Problem Online Judge)是一个在线的编程竞赛平台,它提供了许多编程题目供参赛者解决,以提升编程能力和算法理解。 描述中提到的“叉积+深搜...
- 示例题目:POJ 3349, POJ 3274, POJ 2151, POJ 1840, POJ 2002, POJ 2503 ##### 2. 图算法 - **最短路径**:包括迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)等,适用于求解两点之间的最短...
根据给定的信息,我们可以将这些知识点分为几个大类别:数据结构、图论、搜索算法、动态规划、数学问题以及字符串处理等。 ### 数据结构 #### 队列 - **题目示例**: - POJ 3295:考察队列的基本应用。 #### ...