- 浏览: 583845 次
- 来自: ...
文章分类
最新评论
-
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 3660题目(poj1475):推箱子,要求箱子移动步骤最小。如图:T ... -
图的深搜+回溯练习题:POJ2197
2013-01-18 15:53 1526POJ 2197题意: 给定n个城市及其之间的距离,以及距 ... -
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2326北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1945import java.util.*; ... -
田忌赛马: POJ 2287(贪心解法)
2013-01-03 19:24 2981POJ 2287问题描述: 你一定听过田忌赛马的故事吧? ... -
滚动数组应用:POJ 1159
2012-12-29 21:52 1431POJ 1159题意: 回文词是一种对称的字符串。任意给 ... -
POJ2092:计数排序,求第K大的元素
2012-12-27 08:31 1848题目大意: 输入N和M,N就是N次测试,M是说每次测试产生 ... -
直接插入排序练习:POJ 2388
2012-12-26 09:42 1593关于直接插入排序请参看:http://128kj.iteye. ... -
堆排序练习:POJ 2388
2012-12-26 09:27 1822关于堆排序请参看:http://128kj.iteye.com ... -
大(小)顶堆练习:POJ 1442
2012-12-24 20:58 1807POJ1442题意: ADD(a)表示向集合中增加元素a ... -
极角排序:POJ 1696(叉积+深搜)
2012-12-19 16:12 1725POJ1696题意: 一只很 ... -
凸包练习: POJ 2187(JAVA)
2012-12-17 19:31 1563分治化求凸包,请参看:http://128kj.iteye.c ... -
学习凸包(三):凸包练习 POJ 1113
2012-12-16 14:50 2173接上文:学习凸包(二) ... -
二维树状数组练习 POJ 2029
2012-12-13 19:53 1499关于二维树状数组请参 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1354接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2418当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 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 1748关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1700一、树状数组是干什么的? 平常我们会遇到一些对数组进 ...
相关推荐
NULL 博文链接:https://128kj.iteye.com/blog/1753387
NULL 博文链接:https://128kj.iteye.com/blog/1757060
NULL 博文链接:https://128kj.iteye.com/blog/1754177
NULL 博文链接:https://128kj.iteye.com/blog/1749213
NULL 博文链接:https://128kj.iteye.com/blog/1744222
NULL 博文链接:https://128kj.iteye.com/blog/1759266
NULL 博文链接:https://128kj.iteye.com/blog/1750462
NULL 博文链接:https://128kj.iteye.com/blog/1754170
NULL 博文链接:https://128kj.iteye.com/blog/1744555
NULL 博文链接:https://128kj.iteye.com/blog/1772172
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
poj训练 c语言poj训练 西工大 poj 100题。
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第二季习题,一共15题全部都有,便捷广大西北工业大学大一的孩子。
NULL 博文链接:https://128kj.iteye.com/blog/1746750
西北工业大学poj 已试过 AC 2013年最新整理
2013年最新西工大poj习题,有题,有答案。
西北工业大学POJ作业100份源代码. 每个人的poj顺序是不一样的, 不过还是有参考价值的.