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

大(小)顶堆练习:POJ 1442

阅读更多
POJ1442题意:
   ADD(a)表示向集合中增加元素a,get表示取出第k小元素,k根据get出现的次数不断变化,出现多少次取第几小数。
样例:

Sample Input

7 4
3 1 -4 2 8 -1000 2
1 2 6 6
Sample Output

3
3
1
2

解释:
输入 n = 7 m =4,然后第一行输入n个数,然后另一行输入m个数

index = 1

1:输出n个数中前1个数中的第Index(1)小值

index=2

2:输出n个数中前2个数中的第index(2)小值

index=3

6:输出n个数中前6个数中的第index(3)小值

index=4

6:输出n个数中前6个数中的第index(4)小值


输入保证m个数单调递增

题解:每次取第k小元素,k不断更新。使用两个堆,来完成。 小顶堆负责,选出最小的元素,大顶堆负责,选出k个元素中最大的元素,即第k小元素


import java.util.Scanner;

  public class Main{
   int tree1[];//大顶堆   
   int k1;  
   int tree2[];//小顶堆   
   int k2;  
   int M, N;  
   int A[];  
  
  public Main(){
   }

  //tree:大顶堆
  void build1(int[] tree, int k)  //从下标k开始,大堆向上调整到根
  {  
    int p = k;  
    while(p != 1)  
    {  
        if(tree[p] > tree[p / 2])  //如果大于父亲
        {  
            int temp = tree[p];  //交换
            tree[p] = tree[p / 2];  
            tree[p / 2] = temp;  
        }  
        p = p / 2;  //指向父亲
    }  
}  
  //tree:小顶堆
void build2(int[] tree, int k)  //从k开始,小堆向上调整
{  
    int p = k;  
    while(p != 1)  
    {  
        if(tree[p] < tree[p / 2])  //如果小于交亲
        {  
            int temp = tree[p];  //交换
            tree[p] = tree[p / 2];  
            tree[p / 2] = temp;  
        }  
        p = p / 2;  //指向父亲
    }  
}  
  
//tree:大顶堆
void update1(int[] tree, int k){//向下调整大顶堆的根.  
    int p = 1;  //指向根
    while(2 * p <= k)  
    {  
        int son;  
        if(2 * p == k || tree[2 * p] > tree[2 * p + 1])  
            son = 2 * p;  
        else  
            son = 2 * p + 1;  
        if(tree[p] < tree[son])  //如果父节点的值小于左右儿子中最大者,交换
        {  
            int temp = tree[p];  
            tree[p] = tree[son];  
            tree[son] = temp;  
        }  
        p = son;  //指向儿子节点
    }  
}  
  
//tree:小顶堆
void update2(int[] tree, int k)  //向下调整小顶堆的根,直到k
{  
    int p = 1;  
    while(2 * p <= k)  
    {  
        int son;  
        if(2 * p == k || tree[2 * p] < tree[2 * p + 1])  //取左右儿子中的较小者
            son = 2 * p;  
        else  
            son = 2 * p + 1;  
        if(tree[p] > tree[son])  //如果父节点的值大于左右儿子中最大者,交换
        {  
            int temp = tree[p];  
            tree[p] = tree[son];  
            tree[son] = temp;  
        }  
        p = son;  
    }  
}  
  
  public void  go(){  
   Scanner in=new Scanner(System.in);
    while(in.hasNext())  
    {  
     M=in.nextInt();
     N=in.nextInt();

     A=new int[M+1];
     tree1=new int[M+1];
     tree2=new int[M+1];
     for(int i = 1; i <= M; ++ i)  
            A[i]=in.nextInt();//将M个元素全部读入A
  
        int pre = 0;  
        k1 = k2 = 0;  
        for(int i = 1; i <= N; ++ i)  //共N轮
        {  
            int a=in.nextInt();  
            for(int j = pre + 1; j <= a; ++ j)  //从A中读入前a个元素到tree2
            {  
                tree2[++k2] = A[j];  //读一个,调整一个
                build2(tree2, k2);  //构建tree2使之成为最小堆
                  
            }  
            pre = a;  
            tree1[++ k1] = tree2[1];  //将最小堆的堆顶元素放入tree1中
            build1(tree1, k1);  //构建tree1使之成为最大堆
            tree2[1] = tree2[k2 --];  //删除最小堆的堆顶元素,最小堆的最后一个元素放到堆顶
            update2(tree2, k2);  //调整,使tree2成为小顶堆
            while(k2 != 0 && tree1[1] > tree2[1])  
            {  
                int temp = tree1[1];  
                tree1[1] = tree2[1];  
                tree2[1] = temp;  
                update1(tree1, k1);  //调整,使tree1成为大顶堆
                update2(tree2, k2);  //调整,使tree2成为小顶堆
            }  
            System.out.printf("%d\n", tree1[1]);  
        }         
    }
  }  
    
  public static void main(String args[]){
       Main ma=new Main();
       ma.go();
  }
}
分享到:
评论

相关推荐

    大顶堆应用:POJ2010

    标题“大顶堆应用:POJ2010”指的是一个关于大顶堆算法在解决实际问题中的应用,特别是针对编程竞赛网站POJ(Programming Online Judge)上的问题2010。大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其...

    堆排序练习:POJ 2388

    标题“堆排序练习:POJ 2388”指的是一个关于使用堆排序算法解决编程竞赛问题的实践案例。在编程竞赛中,如POJ(Programming Online Judge)平台上的问题2388,参赛者经常需要高效地解决排序问题,而堆排序作为一种...

    Algorithm-ACM-ICPC-Algorithms.zip

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

    Delphi 12.3控件之TraeSetup-stable-1.0.12120.exe

    Delphi 12.3控件之TraeSetup-stable-1.0.12120.exe

    基于GPRS,GPS的电动汽车远程监控系统的设计与实现.pdf

    基于GPRS,GPS的电动汽车远程监控系统的设计与实现.pdf

    基于MATLAB/Simulink 2018a的单机无穷大系统暂态稳定性仿真与故障分析

    内容概要:本文详细介绍了如何利用MATLAB/Simulink 2018a进行单机无穷大系统的暂态稳定性仿真。主要内容包括搭建同步发电机模型、设置无穷大系统等效电源、配置故障模块及其控制信号、优化求解器设置以及绘制和分析转速波形和摇摆曲线。文中还提供了多个实用脚本,如故障类型切换、摇摆曲线计算和极限切除角的求解方法。此外,作者分享了一些实践经验,如避免常见错误和提高仿真效率的小技巧。 适合人群:从事电力系统研究和仿真的工程师和技术人员,尤其是对MATLAB/Simulink有一定基础的用户。 使用场景及目标:适用于需要进行电力系统暂态稳定性分析的研究项目或工程应用。主要目标是帮助用户掌握单机无穷大系统的建模和仿真方法,理解故障对系统稳定性的影响,并能够通过仿真结果评估系统的性能。 其他说明:文中提到的一些具体操作和脚本代码对于初学者来说可能会有一定的难度,建议结合官方文档或其他教程一起学习。同时,部分技巧和经验来自于作者的实际操作,具有一定的实用性。

    【KUKA 机器人资料】:KUKA机器人剑指未来——访库卡自动化设备(上海)有限公司销售部经理邹涛.pdf

    KUKA机器人相关资料

    基于DLR模型的PM10–能见度–湿度相关性 研究.pdf

    基于DLR模型的PM10–能见度–湿度相关性 研究.pdf

    MATLAB/Simulink中基于电导增量法的光伏并网系统MPPT仿真及其环境适应性分析

    内容概要:本文详细介绍了如何使用MATLAB/Simulink进行光伏并网系统的最大功率点跟踪(MPPT)仿真,重点讨论了电导增量法的应用。首先阐述了电导增量法的基本原理,接着展示了如何在Simulink中构建光伏电池模型和MPPT控制系统,包括Boost升压电路的设计和PI控制参数的设定。随后,通过仿真分析了不同光照强度和温度条件对光伏系统性能的影响,验证了电导增量法的有效性,并提出了针对特定工况的优化措施。 适合人群:从事光伏系统研究和技术开发的专业人士,尤其是那些希望通过仿真工具深入理解MPPT控制机制的人群。 使用场景及目标:适用于需要评估和优化光伏并网系统性能的研发项目,旨在提高系统在各种环境条件下的最大功率点跟踪效率。 其他说明:文中提供了详细的代码片段和仿真结果图表,帮助读者更好地理解和复现实验过程。此外,还提到了一些常见的仿真陷阱及解决方案,如变步长求解器的问题和PI参数整定技巧。

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

    KUKA机器人相关文档

    风力发电领域双馈风力发电机(DFIG)Simulink模型的构建与电流电压波形分析

    内容概要:本文详细探讨了双馈风力发电机(DFIG)在Simulink环境下的建模方法及其在不同风速条件下的电流与电压波形特征。首先介绍了DFIG的基本原理,即定子直接接入电网,转子通过双向变流器连接电网的特点。接着阐述了Simulink模型的具体搭建步骤,包括风力机模型、传动系统模型、DFIG本体模型和变流器模型的建立。文中强调了变流器控制算法的重要性,特别是在应对风速变化时,通过实时调整转子侧的电压和电流,确保电流和电压波形的良好特性。此外,文章还讨论了模型中的关键技术和挑战,如转子电流环控制策略、低电压穿越性能、直流母线电压脉动等问题,并提供了具体的解决方案和技术细节。最终,通过对故障工况的仿真测试,验证了所建模型的有效性和优越性。 适用人群:从事风力发电研究的技术人员、高校相关专业师生、对电力电子控制系统感兴趣的工程技术人员。 使用场景及目标:适用于希望深入了解DFIG工作原理、掌握Simulink建模技能的研究人员;旨在帮助读者理解DFIG在不同风速条件下的动态响应机制,为优化风力发电系统的控制策略提供理论依据和技术支持。 其他说明:文章不仅提供了详细的理论解释,还附有大量Matlab/Simulink代码片段,便于读者进行实践操作。同时,针对一些常见问题给出了实用的调试技巧,有助于提高仿真的准确性和可靠性。

    linux之用户管理教程.md

    linux之用户管理教程.md

    三菱PLC与组态王构建3x3书架式堆垛立体库:IO分配、梯形图编程及组态画面设计

    内容概要:本文详细介绍了利用三菱PLC(特别是FX系列)和组态王软件构建3x3书架式堆垛式立体库的方法。首先阐述了IO分配的原则,明确了输入输出信号的功能,如仓位检测、堆垛机运动控制等。接着深入解析了梯形图编程的具体实现,包括基本的左右移动控制、复杂的自动寻址逻辑,以及确保安全性的限位保护措施。还展示了接线图和原理图的作用,强调了正确的电气连接方式。最后讲解了组态王的画面设计技巧,通过图形化界面实现对立体库的操作和监控。 适用人群:从事自动化仓储系统设计、安装、调试的技术人员,尤其是熟悉三菱PLC和组态王的工程师。 使用场景及目标:适用于需要提高仓库空间利用率的小型仓储环境,旨在帮助技术人员掌握从硬件选型、电路设计到软件编程的全流程技能,最终实现高效稳定的自动化仓储管理。 其他说明:文中提供了多个实用的编程技巧和注意事项,如避免常见错误、优化性能参数等,有助于减少实际应用中的故障率并提升系统的可靠性。

    基于STM32的循迹避障小车仿真20250426(带讲解视频)

    基于STM32的循迹避障小车 主控:STM32 显示:OLED 电源模块 舵机云台 超声波测距 红外循迹模块(3个,左中右) 蓝牙模块 按键(6个,模式和手动控制小车状态) TB6612驱动的双电机 功能: 该小车共有3种模式: 自动模式:根据红外循迹和超声波测距模块决定小车的状态 手动模式:根据按键的状态来决定小车的状态 蓝牙模式:根据蓝牙指令来决定小车的状态 自动模式: 自动模式下,检测距离低于5cm小车后退 未检测到任何黑线,小车停止 检测到左边或左边+中间黑线,小车左转 检测到右边或右边+中间黑线,小车右转 检测到中边或左边+中间+右边黑线,小车前进 手动模式:根据按键的状态来决定小车的状态 蓝牙模式: //需切换为蓝牙模式才能指令控制 *StatusX X取值为0-4 0:小车停止 1:小车前进 2:小车后退 3:小车左转 4:小车右转

    海西蒙古族藏族自治州乡镇边界,矢量边界,shp格式

    矢量边界,行政区域边界,精确到乡镇街道,可直接导入arcgis使用

    基于IEEE33节点的主动配电网优化:含风光储柴燃多源调度模型的经济运行研究

    内容概要:本文探讨了基于IEEE33节点的主动配电网优化方法,旨在通过合理的调度模型降低配电网的总运行成本。文中详细介绍了模型的构建,包括风光发电、储能装置、柴油发电机和燃气轮机等多种分布式电源的集成。为了实现这一目标,作者提出了具体的约束条件,如储能充放电功率限制和潮流约束,并采用了粒子群算法进行求解。通过一系列实验验证,最终得到了优化的分布式电源运行计划,显著降低了总成本并提高了系统的稳定性。 适合人群:从事电力系统优化、智能电网研究的专业人士和技术爱好者。 使用场景及目标:适用于需要优化配电网运行成本的研究机构和企业。主要目标是在满足各种约束条件下,通过合理的调度策略使配电网更加经济高效地运行。 其他说明:文章不仅提供了详细的理论推导和算法实现,还分享了许多实用的经验技巧,如储能充放电策略、粒子群算法参数选择等。此外,通过具体案例展示了不同电源之间的协同作用及其经济效益。

    【KUKA 机器人资料】:KUKA 机器人初级培训教材.pdf

    KUKA机器人相关文档

    基于MATLAB的CSP电站与ORC综合能源系统优化建模及应用

    内容概要:本文详细介绍了将光热电站(CSP)和有机朗肯循环(ORC)集成到综合能源系统中的优化建模方法。主要内容涵盖系统的目标函数设计、关键设备的约束条件(如CSP储热罐、ORC热电耦合)、以及具体实现的技术细节。文中通过MATLAB和YALMIP工具进行建模,采用CPLEX求解器解决混合整数规划问题,确保系统在经济性和环境效益方面的最优表现。此外,文章还讨论了碳排放惩罚机制、风光弃能处理等实际应用场景中的挑战及其解决方案。 适合人群:从事综合能源系统研究的专业人士,尤其是对光热发电、余热利用感兴趣的科研工作者和技术开发者。 使用场景及目标:适用于需要评估和优化包含多种能源形式(如光伏、风电、燃气锅炉等)在内的复杂能源系统的项目。目标是在满足供电供热需求的同时,最小化运行成本并减少碳排放。 其他说明:文中提供了大量具体的MATLAB代码片段作为实例,帮助读者更好地理解和复现所提出的优化模型。对于初学者而言,建议从简单的确定性模型入手,逐渐过渡到更复杂的随机规划和鲁棒优化。

    网站设计与管理作业一.ppt

    网站设计与管理作业一.ppt

Global site tag (gtag.js) - Google Analytics