`
128kj
  • 浏览: 599966 次
  • 来自: ...
社区版块
存档分类
最新评论

大顶堆应用:POJ2010

阅读更多
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源码:
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); 
   
   } 
}


分享到:
评论

相关推荐

    大(小)顶堆练习:POJ 1442

    标题 "大(小)顶堆练习:POJ 1442" 提示我们这是一个关于数据结构和算法的练习题目,特别关注大顶堆或小顶堆的应用。在计算机科学中,大顶堆和小顶堆是两种特殊的二叉堆,它们分别保证了根节点是其子树中最大或最小...

    滚动数组应用:POJ 1159

    标题“滚动数组应用:POJ 1159”指的是一个关于编程竞赛问题的解决方案,该问题在POJ(Programming Online Judge)平台上被提出。滚动数组是一种优化动态规划算法的技术,通过巧妙地重用和更新已经计算过的状态,减少...

    ACMer需要掌握的算法讲解 (2).docx

    * 并查集的高级应用:POJ1703、POJ2492 * KMP算法:POJ1961、POJ2406 * 左偏树(可合并堆) 四、搜索 * 最优化剪枝和可行性剪枝 * 较为复杂的动态规划:POJ1191、POJ1054、POJ3280、POJ2029、POJ2948、POJ1925、...

    堆排序练习:POJ 2388

    堆排序是一种基于比较的排序算法,它的核心思想是构建和维护一个大顶堆或小顶堆。大顶堆中,每个父节点的值都大于或等于其子节点;小顶堆则相反。通过不断调整堆,将最大元素(大顶堆)或最小元素(小顶堆)移动到堆...

    凸包练习: POJ 2187(JAVA)

    总结起来,"凸包练习: POJ 2187(JAVA)"是一个关于几何算法的实际应用问题,通过解决这个问题,你可以学习到如何用JAVA编程语言处理几何问题,掌握凸包算法,以及如何有效地读取、处理和输出数据。同时,这也是提升...

    ACM常用算法及其相应的练习题 (2).docx

    (1) C++的标准模版库的应用:poj3096, poj3007 (2) 较为复杂的模拟题的训练:poj3393, poj1472, poj3371, poj1027, poj2706 (3) 差分约束系统的建立和求解:poj1201, poj2983 (4) 最小费用最大流:poj2516, poj2516,...

    树状数组练习:POJ 2481(JAVA)

    【描述】虽然描述部分为空,但我们可以推测,作者在博客中可能详细解释了树状数组的概念、特性以及其在解决实际问题中的应用。通常,这样的文章会包含以下几个方面: 1. **树状数组定义**:树状数组是一种高效的...

    ACM 题型

    - 示例题目:poj1191, poj1054, poj3280, poj2029, poj2948, poj1925, poj3034 2. **四边形不等式** - 示例题目:POJ3254, poj2411, poj1185 3. **记忆化搜索** - 示例题目:poj2057, poj1947, poj2486, poj...

    田忌赛马: POJ 2287(贪心解法)

    POJ(Programming Online Judge)是国内外广受欢迎的在线编程评测系统,其中的2287题正是以"田忌赛马"为背景的算法问题,主要考察选手对贪心策略的理解和应用。 贪心算法是一种在每一步选择中都采取当前状态下最好...

    树状数组练习:POJ 3067

    在这个问题中,我们通过分析POJ 3067的题目来探讨如何应用树状数组解决实际问题。 POJ 3067题目大致是这样的:给定一个数组,我们需要在数组上进行一系列的查询和修改操作。查询操作询问区间内元素之和,而修改操作...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **解释**:这一类问题通常涉及基本的数学运算和数学定理的应用。 #### 2. 几何问题 - **例题**:poj1328, poj2109, poj2586 - **解释**:这类题目涉及到几何图形的处理,比如点、线、面等的计算与判断。 #### 3....

    poj题目分类

    * C++的标准模版库的应用:例如 poj3096、poj3007。 * 较为复杂的模拟题的训练:例如 poj3393、poj1472、poj3371、poj1027、poj2706。 2. 图算法: * 差分约束系统的建立和求解:例如 poj1201、poj2983。 * ...

    直接插入排序练习:POJ 2388

    - 为了优化性能,可以考虑使用二分查找法找到待插入元素的正确位置,但这通常只在数组部分有序或元素数量较大时才有效。 - 在实际编程中,通常会使用一个循环来遍历数组的剩余部分,进行插入操作。对于POJ 2388这个...

    ACM常用算法及其相应的练习题.docx

    + poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...

    ACM常用算法及其相应的练习题 (2).pdf

    * C++的标准模版库的应用:C++的标准模版库是指C++语言的标准库,提供了许多有用的算法和数据结构。例题:poj3096、poj3007。 * 较为复杂的模拟题的训练:较为复杂的模拟题是指需要使用多种算法和数据结构来解决的...

    图的深搜+回溯练习题:POJ2197

    标题中的“图的深搜+回溯练习题:POJ2197”是指一个编程题目,主要涉及图论中的深度优先搜索(DFS, Depth First Search)和回溯算法的应用。这个题目来源于在线编程竞赛平台POJ(Problem Online Judge),编号为2197...

    极角排序:POJ 1696(叉积+深搜)

    在POJ 1696这个编程题目中,很可能需要解决与极角排序相关的问题。POJ(Problem Online Judge)是一个在线的编程竞赛平台,它提供了许多编程题目供参赛者解决,以提升编程能力和算法理解。 描述中提到的“叉积+深搜...

    ACM 新手指南 PKU 题目分类

    - 示例题目:POJ 3349, POJ 3274, POJ 2151, POJ 1840, POJ 2002, POJ 2503 ##### 2. 图算法 - **最短路径**:包括迪杰斯特拉算法(Dijkstra)、贝尔曼-福特算法(Bellman-Ford)等,适用于求解两点之间的最短...

    经典 的POJ 分类

    根据给定的信息,我们可以将这些知识点分为几个大类别:数据结构、图论、搜索算法、动态规划、数学问题以及字符串处理等。 ### 数据结构 #### 队列 - **题目示例**: - POJ 3295:考察队列的基本应用。 #### ...

Global site tag (gtag.js) - Google Analytics