当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

大顶堆应用:POJ2010

发表于: 2012-12-23   作者:128kj   来源:转载   浏览:
摘要: POJ2010题意:     奶牛学校招生,c头奶牛报名,要选n头(n为奇数),学校是义务制,所以每头奶牛的学费都由学校负责。每头奶牛都由自己的考试分数和它需要花的学费,学校总共有f的资金,问合法招生方案中中间分数(即排名第(n+1)/2)最高的是多少。 题解:先将所有的奶牛按照分数由低到高排序,假设k是招的奶牛中排名中间的那头,按照排序可知,[1,k-1]中
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); 
   
   } 
}


大顶堆应用:POJ2010

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
小(大)顶堆的实现 1. 用数组表示二叉树 二叉树表示如下图: 用数组表示二叉树 2 3 4 6 8 A0 A1 A2
一如既往,先上详细的过程图。 应用场景 比如求10亿个数中的最大的前10个数,时时构建只有10个元素
一:二叉堆以及相关操作 二:例题 二叉堆是一个逻辑结构像堆的一个数据结构 对于这个堆,采用一维数
什么是堆: 堆的定义:n个元素的序列k={k0,k1,……,kn-1},当且仅满足条件 (1)ki >= k2i+1 和 ki
简介 关于堆和PriorityQueue的思想和实现,前面的几篇文章我都有详细的描述,比如堆排序的实现和Pri
问题描述:考察一个机械厂,其中有 m 台一模一样的机器。现有 n 个作业需要处理,设作业 i 的处理时
7
堆的定义 一些按照重要性或者优先级来组织的对象称为优先队列。 堆是一棵完全二叉树,由数组来实现
8
堆 本文我们重点讨论堆,堆分为最小堆和最大堆两种,由于两者操作操作类似,所以我们只讨论最小堆(
9
在求前K大数中可以用堆来维护,但是很久没碰堆这个东西了,BS下自己。重新复习一下吧。 插入堆的时
建立Huffman树的基本思路:给定有权重的一系列数据(带权重),从中挑选最小权重的两个数据,组成一
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号