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

大顶堆应用: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 2388

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

    Algorithm-ACM-ICPC-Algorithms.zip

    对于ACM/ICPC而言,平衡树(如AVL树、红黑树)、堆(大顶堆、小顶堆)、斐波那契堆等高级数据结构的理解和运用,能够显著提高算法效率。 六、模拟和暴力求解 在无法直接找到高效算法的情况下,模拟和暴力求解也是...

    基于单片机的科学型计算器设计(51+1602+KEY40)#0067

    包括:源程序工程文件、Proteus仿真工程文件、配套技术手册等 1、采用51/52单片机作为主控芯片; 2、采用1602液晶显示; 3、采用5*8矩阵键盘输入; 4、功能键包括:复位键(RST),回删键(DEL),确定键(OK),第二功能切换(2U),背光灯键(LED); 5、运算均为单精度浮点数,包括: 加(+),减(-),乘(x),除(÷), e底指数(e^n),N次方(x^n),开N次方(sqrt), 正弦(sin),余弦(cos),正切(tan), 对数(log), 阶乘(n!)(n<35), 排列(Arn), 累加(∑), *开启第二功能(2U)后可用: 反正弦(asin),反余弦(acos),反正切(atan), 组合(Crn)

    基于三菱FX2N PLC的机械手控制系统设计与实现

    内容概要:本文详细介绍了如何利用三菱FX2N系列PLC构建机械手控制系统。主要内容涵盖电路图设计、IO表配置、源程序编写以及单机组态。文中提供了具体的梯形图编程实例,展示了如何通过PLC精确控制机械手的各种动作,如抓取、移动和放置。此外,还分享了许多实用的调试技巧和注意事项,强调了传感器状态交叉验证和关键动作的时间守护机制。通过这些内容,读者可以全面了解PLC在机械手控制中的应用。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是对PLC编程和机械手控制感兴趣的初学者和有一定经验的研发人员。 使用场景及目标:适用于需要设计和实施机械手控制系统的工业场合,帮助工程师掌握PLC编程技巧,提高机械手控制系统的稳定性和可靠性。 其他说明:文章不仅提供理论指导,还包括大量实战代码和调试经验,有助于读者快速上手并在实践中不断优化系统性能。

    豆包生成美女的AI提示词基于豆包平台的美女图像生成提示词

    内容概要:本文档提供了用于生成具有时尚性感元素的美女跳舞图像的提示词指南。文档内容包括角色设定为擅长描绘时尚与超现实主义图片的创作者,背景设定强调女性形象,偏好展现性感漂亮女孩的镜头表达。目标在于根据用户指令创作三幅统一风格的图像,注重色彩搭配和高清效果,同时确保每张图片都具备半身像、真实感和电影效果的特点。文档还给出了具体的输出示例,详细描述了人物形象、服装搭配以及场景布置等要素,旨在为用户提供满意的图像生成服务。; 适合人群:对图像生成感兴趣,尤其是喜欢带有时尚性感元素的美女图像的用户。; 使用场景及目标:①根据用户提供的简单场景信息(如户外或室内)生成三幅不同场景但风格统一的赛博朋克风格美女跳舞图像;②确保生成的图像符合特定的要求,如半身像、真实感、电影效果、性感服装、特定灯光效果等;③通过询问用户对生成图像的满意度来保证服务质量。; 其他说明:文档明确了图像生成的工作流程,从接收用户指令到根据反馈调整生成内容,确保整个过程高效且满足用户需求。同时,文档还限制了生成图像的具体条件,如场景必须为赛博朋克风格、不能出现鞋子和其他人等,以保证图像的独特性和一致性。

    蓝桥杯大赛模拟题PDF

    题目描述 1.问题描述 一个正整数如果任何一个数位不大于右边相邻的数位,则称为一个数位递增的 数,例如1135是一个数位递增的数,而1024不是一个数位递增的数。 给定正整数n,请问在整数1至n中有多少个数位递增的数? 输入格式 输入的第一行包含一个整数n。 输出格式 输出一行包含一个整数,表示答案。 样例输入 30 样例输出

    基于非对称纳什谈判的多微网电能共享优化策略及其MATLAB实现

    内容概要:本文详细介绍了基于非对称纳什谈判的多微网电能共享运行优化策略及其MATLAB代码实现。首先阐述了纳什谈判和合作博弈的基本理论,然后将多微网电能共享合作运行模型分解为微网联盟效益最大化和合作收益分配两个子问题。文中展示了如何通过交替方向乘子法(ADMM)进行分布式求解,确保各微网隐私安全。此外,还探讨了电转气(P2G)和碳捕集(CCS)设备的应用,以实现低碳调度。最后,通过具体代码示例解释了模型的构建、求解及优化过程。 适合人群:对电力系统优化、博弈论、MATLAB编程感兴趣的科研人员和技术开发者。 使用场景及目标:适用于希望深入了解多微网电能共享优化策略的研究者,旨在提高微网联盟的整体效益并实现公平合理的收益分配。同时,该策略有助于降低碳排放,提升系统的环境友好性和经济性。 其他说明:文章提供了详细的代码注释和调试技巧,帮助读者更好地理解和实现这一复杂的优化策略。

    MATLAB机器人仿真:基于视觉控制的六轴机械臂运动路径规划与实现

    内容概要:本文详细介绍了如何利用MATLAB进行六轴机械臂的视觉控制系统仿真。首先,通过MATLAB的图像处理工具箱捕捉并处理实时视频流,使用HSV颜色空间进行颜色阈值处理,从而定位红色小球的位置。然后,借助Robotics Toolbox中的逆运动学模块,将摄像头获取的目标位置转换为机械臂的关节角度,确保机械臂能够精准地追踪目标。此外,还讨论了路径规划的方法,如使用五次多项式插值和平滑滤波器,使机械臂的动作更加流畅。文中强调了实际应用中可能遇到的问题及其解决方法,如奇异点处理、坐标系转换和机械臂的速度限制等。 适合人群:具有一定编程基础和技术背景的研究人员、工程师以及对机器人视觉控制感兴趣的开发者。 使用场景及目标:适用于希望在MATLAB环境中快速搭建和测试机械臂视觉控制系统的科研人员和工程师。主要目标是掌握从图像处理到机械臂控制的完整流程,理解各模块的工作原理,并能够在实际项目中应用。 其他说明:本文不仅提供了详细的代码示例,还分享了许多实用的经验和技巧,帮助读者更好地理解和优化仿真系统。同时提醒读者注意仿真与现实之间的差异,如摄像头延迟、机械臂传动误差等问题。

    【KUKA 机器人坐标的建立】:mo2_base_en.ppt

    KUKA机器人相关文档

    【KUKA 机器人资料】:KAKA机器人汽车座椅测试系统.pdf

    KUKA机器人相关文档

    三相变流器MPC控制:Matlab/Simulink仿真实现及优化技巧

    内容概要:本文详细介绍了三相变流器的模型预测控制(MPC)在Matlab/Simulink环境下的实现过程。首先,初始化程序设置了关键参数,如直流母线电压、开关频率和控制周期等,确保系统的稳定性和效率。接着,通过MPC_sfun.c实现了核心控制算法,采用状态空间模型进行滚动预测,提高了系统的动态响应能力。最后,利用out.m生成高质量的仿真结果图,展示了负载突变时的快速恢复特性,并提供了优化建议,如调整代价函数权重和引入软约束等。 适合人群:电力电子工程师、控制系统研究人员以及对MPC感兴趣的科研工作者。 使用场景及目标:适用于需要精确控制电压电流的场合,如电动汽车充电站、风力发电系统等。主要目标是提高系统的动态响应速度、降低总谐波失真(THD),并在性能和计算负担之间取得平衡。 其他说明:文中提到了一些实用技巧,如控制周期的选择、预测步长的优化、图形绘制的最佳实践等,有助于读者更好地理解和应用MPC控制策略。同时,强调了在实际应用中需要注意的问题,如避免过高开关频率导致器件损坏等。

    网络炒作策划要点解析.ppt

    网络炒作策划要点解析.ppt

    三菱Q03UDE PLC SFC编程模板在16轴伺服控制系统中的应用与优化

    内容概要:本文详细介绍了三菱Q03UDE PLC使用SFC(顺序功能图)编程方法在16轴伺服控制系统中的应用。文章首先概述了硬件配置,包括500个IO点、16轴伺服控制以及触摸屏的画面编程。接着深入探讨了SFC编程的具体实现方式,如将复杂的轴控制分解为独立的流程块,利用并行结构解决多轴同步问题,通过触摸屏实时监控和反馈SFC步状态,以及如何高效管理和复用输出点。此外,文章还讨论了SFC在状态管理和报警处理方面的优势,并提供了具体的代码示例来展示其实现细节。最后,作者分享了一些实用技巧和注意事项,强调了SFC编程相比传统梯形图的优势。 适合人群:从事工业自动化控制系统的工程师和技术人员,尤其是对三菱PLC和SFC编程感兴趣的读者。 使用场景及目标:适用于需要进行复杂多轴伺服控制项目的工程师,旨在提高调试效率、减少信号冲突、缩短新人培养周期,并提供一种更加直观和高效的编程方法。 其他说明:文中提到的实际项目经验有助于读者更好地理解和应用SFC编程技术,同时也提醒了一些常见的错误和陷阱,帮助读者避免不必要的麻烦。

    LabVIEW与三菱FX3U PLC串口通讯:基于Modbus协议的简易实现及应用

    内容概要:本文详细介绍了如何使用LabVIEW实现与三菱FX3U PLC的串口通讯,采用Modbus无协议通讯方式进行简单读写操作。主要内容包括PLC通讯参数配置、LabVIEW工程结构搭建、Modbus报文构造方法以及具体的读写数据模块实现。文中提供了详细的代码示例和注意事项,帮助读者快速理解和实践这一通讯过程。 适合人群:对工业自动化有一定兴趣的技术人员,尤其是熟悉LabVIEW和三菱PLC的工程师。 使用场景及目标:适用于需要将LabVIEW作为上位机与三菱FX3U PLC进行串口通讯的应用场合,如工业控制系统、实验教学等。主要目标是掌握Modbus协议的基础知识及其在LabVIEW中的具体实现。 其他说明:文章还提供了一些常见的错误排查方法和实用技巧,如CRC校验的处理、地址偏移量的注意事项等。此外,附带了完整的源码供读者下载和参考。

    图像检索-基于零样本开集的草图图像检索系统实现-附项目源码+流程教程-优质项目实战.zip

    图像检索_基于零样本开集的草图图像检索系统实现_附项目源码+流程教程_优质项目实战

    基于C语言写的电话簿程序

    基于C语言写的电话簿程序

    基于单片机的电压(20V)检测设计(51+1602+AD0808)#0063

    包括:源程序工程文件、Proteus仿真工程文件、配套技术手册等 1、采用51单片机作为主控芯片; 2、采用1602液晶显示检测电压值,范围0~20V; 3、采用ADC0808进行模数转换;

    【剧本杀AI提示词指令】基于AI的剧本杀定制化创作系统(deepseek,豆包,kimi,chatGPT,扣子空间,manus,AI训练师)

    内容概要:本文介绍了一个专业的剧本杀创作作家AI。它能根据客户需求创作各种风格和难度的剧本杀剧本,并提供创作建议和修改意见。其目标是创造引人入胜、逻辑严密的剧本体验。它的工作流程包括接收理解剧本要求、创作剧本框架情节、设计角色背景线索任务剧情走向、提供修改完善建议、确保剧本可玩性和故事连贯性。它需保证剧本原创、符合道德法律标准并在规定时间内完成创作。它具备剧本创作技巧、角色构建理解、线索悬念编织、文学知识和创意思维、不同文化背景下剧本风格掌握以及剧本杀游戏机制和玩家心理熟悉等技能。; 适合人群:有剧本杀创作需求的人群,如剧本杀爱好者、创作者等。; 使用场景及目标:①为用户提供符合要求的剧本杀剧本创作服务;②帮助用户完善剧本杀剧本,提高剧本质量。; 阅读建议:此资源详细介绍了剧本杀创作作家AI的功能和服务流程,用户可以依据自身需求与该AI合作,明确表达自己的创作需求并配合其工作流程。

Global site tag (gtag.js) - Google Analytics