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

大(小)顶堆练习: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树、红黑树)、堆(大顶堆、小顶堆)、斐波那契堆等高级数据结构的理解和运用,能够显著提高算法效率。 六、模拟和暴力求解 在无法直接找到高效算法的情况下,模拟和暴力求解也是...

    拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法.pdf

    拟阵约束下最大化子模函数的模型及其算法的一种熵聚类方法.pdf

    电力市场领域中基于CVaR风险评估的省间交易商最优购电模型研究与实现

    内容概要:本文探讨了在两级电力市场环境中,针对省间交易商的最优购电模型的研究。文中提出了一个双层非线性优化模型,用于处理省内电力市场和省间电力交易的出清问题。该模型采用CVaR(条件风险价值)方法来评估和管理由新能源和负荷不确定性带来的风险。通过KKT条件和对偶理论,将复杂的双层非线性问题转化为更易求解的线性单层问题。此外,还通过实际案例验证了模型的有效性,展示了不同风险偏好设置对购电策略的影响。 适合人群:从事电力系统规划、运营以及风险管理的专业人士,尤其是对电力市场机制感兴趣的学者和技术专家。 使用场景及目标:适用于希望深入了解电力市场运作机制及其风险控制手段的研究人员和技术开发者。主要目标是为省间交易商提供一种科学有效的购电策略,以降低风险并提高经济效益。 其他说明:文章不仅介绍了理论模型的构建过程,还包括具体的数学公式推导和Python代码示例,便于读者理解和实践。同时强调了模型在实际应用中存在的挑战,如数据精度等问题,并指出了未来改进的方向。

    MATLAB/Simulink平台下四机两区系统风储联合调频技术及其高效仿真实现

    内容概要:本文探讨了在MATLAB/Simulink平台上针对四机两区系统的风储联合调频技术。首先介绍了四机两区系统作为经典的电力系统模型,在风电渗透率增加的情况下,传统一次调频方式面临挑战。接着阐述了风储联合调频技术的应用,通过引入虚拟惯性控制和下垂控制策略,提高了系统的频率稳定性。文章展示了具体的MATLAB/Simulink仿真模型,包括系统参数设置、控制算法实现以及仿真加速方法。最终结果显示,在风电渗透率为25%的情况下,通过风储联合调频,系统频率特性得到显著提升,仿真时间缩短至5秒以内。 适合人群:从事电力系统研究、仿真建模的技术人员,特别是关注风电接入电网稳定性的研究人员。 使用场景及目标:适用于希望深入了解风储联合调频机制及其仿真实现的研究人员和技术开发者。目标是掌握如何利用MATLAB/Simulink进行高效的电力系统仿真,尤其是针对含有高比例风电接入的复杂场景。 其他说明:文中提供的具体参数配置和控制算法有助于读者快速搭建类似的仿真环境,并进行相关研究。同时强调了参考文献对于理论基础建立的重要性。

    永磁同步电机无感控制:高频方波注入与滑膜观测器结合实现及其应用场景

    内容概要:本文介绍了永磁同步电机(PMSM)无感控制技术,特别是高频方波注入与滑膜观测器相结合的方法。首先解释了高频方波注入法的工作原理,即通过向电机注入高频方波电压信号,利用电机的凸极效应获取转子位置信息。接着讨论了滑膜观测器的作用,它能够根据电机的电压和电流估计转速和位置,具有较强的鲁棒性。两者结合可以提高无传感器控制系统的稳定性和精度。文中还提供了具体的Python、C语言和Matlab代码示例,展示了如何实现这两种技术。此外,简要提及了正弦波注入的相关论文资料,强调了其在不同工况下的优势。 适合人群:从事电机控制系统设计的研发工程师和技术爱好者,尤其是对永磁同步电机无感控制感兴趣的读者。 使用场景及目标:适用于需要减少传感器依赖、降低成本并提高系统可靠性的情况,如工业自动化设备、电动汽车等领域的电机控制。目标是掌握高频方波注入与滑膜观测器结合的具体实现方法,应用于实际工程项目中。 其他说明:文中提到的高频方波注入和滑膜观测器的结合方式,不仅提高了系统的性能,还在某些特殊情况下表现出更好的适应性。同时,附带提供的代码片段有助于读者更好地理解和实践这一技术。

    MATLAB中扩展卡尔曼滤波与双扩展卡尔曼滤波在电池参数辨识的应用

    内容概要:本文深入探讨了MATLAB中扩展卡尔曼滤波(EKF)和双扩展卡尔曼滤波(DEKF)在电池参数辨识中的应用。首先介绍了EKF的基本原理和代码实现,包括状态预测和更新步骤。接着讨论了DEKF的工作机制,即同时估计系统状态和参数,解决了参数和状态耦合估计的问题。文章还详细描述了电池参数辨识的具体应用场景,特别是针对电池管理系统中的荷电状态(SOC)估计。此外,提到了一些实用技巧,如雅可比矩阵的计算、参数初始值的选择、数据预处理方法等,并引用了几篇重要文献作为参考。 适合人群:从事电池管理系统开发的研究人员和技术人员,尤其是对状态估计和参数辨识感兴趣的读者。 使用场景及目标:适用于需要精确估计电池参数的实际项目,如电动汽车、储能系统等领域。目标是提高电池管理系统的性能,确保电池的安全性和可靠性。 其他说明:文章强调了实际应用中的注意事项,如数据处理、参数选择和模型优化等方面的经验分享。同时提醒读者关注最新的研究成果和技术进展,以便更好地应用于实际工作中。

    基于三菱FX3U PLC和威纶通触摸屏的分切机上下收放卷张力控制系统设计

    内容概要:本文详细介绍了在无电子凸轮功能情况下,利用三菱FX3U系列PLC和威纶通触摸屏实现分切机上下收放卷张力控制的方法。主要内容涵盖硬件连接、程序框架设计、张力检测与读取、PID控制逻辑以及触摸屏交互界面的设计。文中通过具体代码示例展示了如何初始化寄存器、读取张力传感器数据、计算张力偏差并实施PID控制,最终实现稳定的张力控制。此外,还讨论了卷径计算、速度同步控制等关键技术点,并提供了现场调试经验和优化建议。 适合人群:从事自动化生产设备维护和技术支持的专业人士,尤其是熟悉PLC编程和触摸屏应用的技术人员。 使用场景及目标:适用于需要对分切机进行升级改造的企业,旨在提高分切机的张力控制精度,确保材料切割质量,降低生产成本。通过本方案可以实现±3%的张力控制精度,满足基本生产需求。 其他说明:本文不仅提供详细的程序代码和硬件配置指南,还分享了许多实用的调试技巧和经验,帮助技术人员更好地理解和应用相关技术。

    基于S7系列PLC与组态王的三泵变频恒压供水系统设计与实现

    内容概要:本文详细介绍了一种基于西门子S7-200和S7-300 PLC以及组态王软件的三泵变频恒压供水系统。主要内容涵盖IO分配、接线图原理图、梯形图程序编写和组态画面设计四个方面。通过合理的硬件配置和精确的编程逻辑,确保系统能够在不同负载情况下保持稳定的供水压力,同时实现节能和延长设备使用寿命的目标。 适合人群:从事工业自动化领域的工程师和技术人员,尤其是熟悉PLC编程和组态软件使用的专业人士。 使用场景及目标:适用于需要稳定供水的各种场合,如住宅小区、工厂等。目标是通过优化控制系统,提升供水效率,减少能源消耗,并确保系统的可靠性和安全性。 其他说明:文中提供了详细的实例代码和调试技巧,帮助读者更好地理解和实施该项目。此外,还分享了一些实用的经验教训,有助于避免常见的错误和陷阱。

    三相三线制SVG/STATCOM的Simulink仿真建模与控制策略解析

    内容概要:本文详细介绍了三相三线制静止无功发生器(SVG/STATCOM)在Simulink中的仿真模型设计与实现。主要内容涵盖ip-iq检测法用于无功功率检测、dq坐标系下的电流解耦控制、电压电流双闭环控制系统的设计、SVPWM调制技术的应用以及具体的仿真参数设置。文中不仅提供了理论背景,还展示了具体的Matlab代码片段,帮助读者理解各个控制环节的工作原理和技术细节。此外,文章还讨论了实际调试中遇到的问题及解决方案,强调了参数调整的重要性。 适合人群:从事电力系统自动化、电力电子技术研究的专业人士,特别是对SVG/STATCOM仿真感兴趣的工程师和研究人员。 使用场景及目标:适用于希望深入了解SVG/STATCOM工作原理并掌握其仿真方法的研究人员和工程师。目标是在实践中能够正确搭建和优化SVG/STATCOM的仿真模型,提高无功补偿的效果。 其他说明:文章提供了丰富的实例代码和调试技巧,有助于读者更好地理解和应用所学知识。同时,文中提及的一些经验和注意事项来源于实际项目,具有较高的参考价值。

    基于SIMULINK的风力机发电效率建模探究.pdf

    基于SIMULINK的风力机发电效率建模探究.pdf

    CarSim与Simulink联合仿真:基于MPC模型预测控制实现智能超车换道

    内容概要:本文介绍了如何将CarSim的动力学模型与Simulink的智能算法相结合,利用模型预测控制(MPC)实现车辆的智能超车换道。主要内容包括MPC控制器的设计、路径规划算法、联合仿真的配置要点以及实际应用效果。文中提供了详细的代码片段和技术细节,如权重矩阵设置、路径跟踪目标函数、安全超车条件判断等。此外,还强调了仿真过程中需要注意的关键参数配置,如仿真步长、插值设置等,以确保系统的稳定性和准确性。 适合人群:从事自动驾驶研究的技术人员、汽车工程领域的研究人员、对联合仿真感兴趣的开发者。 使用场景及目标:适用于需要进行自动驾驶车辆行为模拟的研究机构和企业,旨在提高超车换道的安全性和效率,为自动驾驶技术研发提供理论支持和技术验证。 其他说明:随包提供的案例文件已调好所有参数,可以直接导入并运行,帮助用户快速上手。文中提到的具体参数和配置方法对于初学者非常友好,能够显著降低入门门槛。

    基于MATLAB的信号与系统实验:常见信号生成、卷积积分、频域分析及Z变换详解

    内容概要:本文详细介绍了利用MATLAB进行信号与系统实验的具体步骤和技术要点。首先讲解了常见信号(如方波、sinc函数、正弦波等)的生成方法及其注意事项,强调了时间轴设置和参数调整的重要性。接着探讨了卷积积分的两种实现方式——符号运算和数值积分,指出了各自的特点和应用场景,并特别提醒了数值卷积时的时间轴重构和步长修正问题。随后深入浅出地解释了频域分析的方法,包括傅里叶变换的符号计算和快速傅里叶变换(FFT),并给出了具体的代码实例和常见错误提示。最后阐述了离散时间信号与系统的Z变换分析,展示了如何通过Z变换将差分方程转化为传递函数以及如何绘制零极点图来评估系统的稳定性。 适合人群:正在学习信号与系统课程的学生,尤其是需要完成相关实验任务的人群;对MATLAB有一定基础,希望通过实践加深对该领域理解的学习者。 使用场景及目标:帮助学生掌握MATLAB环境下信号生成、卷积积分、频域分析和Z变换的基本技能;提高学生解决实际问题的能力,避免常见的编程陷阱;培养学生的动手能力和科学思维习惯。 其他说明:文中不仅提供了详细的代码示例,还分享了许多实用的小技巧,如如何正确保存实验结果图、如何撰写高质量的实验报告等。同时,作者以幽默风趣的语言风格贯穿全文,使得原本枯燥的技术内容变得生动有趣。

    【KUKA 机器人移动编程】:mo2_motion_ptp_en.ppt

    KUKA机器人相关文档

    永磁同步电机(PMSM)无传感器控制:I/F启动与滑模观测器结合的技术实现及应用

    内容概要:本文详细介绍了无传感器永磁同步电机(PMSM)控制技术,特别是针对低速和中高速的不同控制策略。低速阶段采用I/F控制,通过固定电流幅值和斜坡加速的方式启动电机,确保平稳启动。中高速阶段则引入滑模观测器进行反电动势估算,从而精确控制电机转速。文中还讨论了两者之间的平滑切换逻辑,强调了参数选择和调试技巧的重要性。此外,提供了具体的伪代码示例,帮助读者更好地理解和实现这一控制方案。 适合人群:从事电机控制系统设计的研发工程师和技术爱好者。 使用场景及目标:适用于需要降低成本并提高可靠性的应用场景,如家用电器、工业自动化设备等。主要目标是掌握无传感器PMSM控制的基本原理及其优化方法。 其他说明:文中提到的实际案例和测试数据有助于加深理解,同时提醒开发者注意硬件参数准确性以及调试过程中可能出现的问题。

    智能家居与物联网培训材料.ppt

    智能家居与物联网培训材料.ppt

    Matlab实现车辆路径规划:基于TSP、CVRP、CDVRP、VRPTW的四大算法解析及应用

    内容概要:本文详细介绍了使用Matlab解决车辆路径规划问题的四种经典算法:TSP(旅行商问题)、CVRP(带容量约束的车辆路径问题)、CDVRP(带容量和距离双重约束的车辆路径问题)和VRPTW(带时间窗约束的车辆路径问题)。针对每个问题,文中提供了具体的算法实现思路和关键代码片段,如遗传算法用于TSP的基础求解,贪心算法和遗传算法结合用于CVRP的路径分割,以及带有惩罚函数的时间窗约束处理方法。此外,还讨论了性能优化技巧,如矩阵运算替代循环、锦标赛选择、2-opt局部优化等。 适合人群:具有一定编程基础,尤其是对物流调度、路径规划感兴趣的开发者和技术爱好者。 使用场景及目标:适用于物流配送系统的路径优化,旨在提高配送效率,降低成本。具体应用场景包括但不限于外卖配送、快递运输等。目标是帮助读者掌握如何利用Matlab实现高效的路径规划算法,解决实际业务中的复杂约束条件。 其他说明:文中不仅提供了详细的代码实现,还分享了许多实践经验,如参数设置、数据预处理、异常检测等。建议读者在实践中不断尝试不同的算法组合和优化策略,以应对更加复杂的实际问题。

    软考网络工程师2010-2014真题及答案

    软考网络工程师2010-2014真题及答案完整版 全国计算机软考 适合软考中级人群

Global site tag (gtag.js) - Google Analytics