首页 > 其他分享 >洛谷 P3378 【模板】堆

洛谷 P3378 【模板】堆

时间:2023-07-09 09:55:21浏览次数:47  
标签:洛谷 int else jh P3378 儿子 模板 op

siftup模板

当然还得有siftdown模板

“稍”加调试,就可以得到模板代码

#include<bits/stdc++.h>
using namespace std;
int n,op,sl=0,h[1000010];
void jh(int x,int y)//交换 
{
    int z=h[x];
    h[x]=h[y];
    h[y]=z;
}
void siftu(int i)//siftup
{
    bool f=true;
    while(f)//因为是小顶堆,所以必须考虑没有儿子的情况 
    {        
        if(i==1 || h[i/2]<=h[i]) 
            //当元素位于堆顶或正确位置时 
            f=false;//跳出循环 
        else
        {
            //元素比它的父亲小,因此交换 
            jh(i,i/2);
            i/=2;
        }
    }
}
void siftd(int i)//siftdown
{
    bool f=true;
    while(f)
    {
        if(i*2+1<=sl)
            //当它有右儿子时 
            if(h[i]>h[i*2+1])
                //它比右儿子大 
                if(h[i*2+1]>h[i*2]) 
                {
                    //右儿子比左儿子大,左儿子最小
                    jh(i,i*2); 
                    i*=2;
                }else
                {
                    //否则交换右儿子 
                    jh(i,i*2+1);
                    i=i*2+1;
                }                                        
            else if(h[i]>h[i*2]) 
            {
                //右儿子比它大,但左儿子比它小
                jh(i,i*2);
                i*=2;
            }else
                //两个儿子都比他小,到达正确位置 
                f=false;
        else if(i*2<=sl)
            //它没有右儿子,但有左儿子 
            if(h[i]>h[i*2])
            {
                jh(i,i*2);
                i*=2;
            }else
                f=false;
        else
            //没有儿子(就很惨),位置一定正确 
            f=false;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>op;
        if(op==1)
        {
            sl++;//堆的数量增加 
            cin>>h[sl];//在末尾输入 
            siftu(sl); 
        }else if(op==2)
            cout<<h[1]<<endl;
        else if(op==3)
        {
            h[1]=h[sl];//将末位元素直接覆盖到堆顶 
            sl--;//数量减少 
            siftd(1);
        } 
    }
    
    return 0;
} 

如果没看懂,很正常,再看一遍,或者再继续理解小顶堆的基本逻辑

如果看懂了上面的算法,事情就变得简单了,就可以理解并轻松使用c++提供的STL来完成

#include<bits/stdc++.h>
using namespace std;
int n,op,sr;
int main()
{
    priority_queue< int,vector<int>,greater<int> >h;
    //定义 
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>op;
        if(op==1)
        {
            cin>>sr;
            h.push(sr);
        }else if(op==2)
            cout<<h.top()<<endl;
        else if(op==3)
        {
            h.pop();
        }
    }
    
    return 0;
}

 

标签:洛谷,int,else,jh,P3378,儿子,模板,op
From: https://www.cnblogs.com/fc2110rxr/p/17538352.html

相关文章

  • 命令模式和模板模式以及构造者模式在工程中的应用
     在开发springboot项目的开发过程中我们总会使用到mvc模式,在controller层写接口,service中写业务,dao层进行数据持久化。这种模式总会service的实现层写很多代码,这样会使得seviceimpl类中有很多业务代码,以及注入很多的bean,后期维护起来会相当麻烦。今天采用命令模式,模板模式来实现......
  • c++模板相关学习--泛型编程
     类模板基础#define_CRT_SECURE_NO_WARNINGS#include<iostream>usingnamespacestd;#include<string>template<classNAMETYPE,classAGETYPE=int>//类模板中可以有默认参数classPerson{public:Person(NAMETYPEname,AGETYPEage){......
  • [模板]01trie,维护异或最大值
    //查询异或最大值,每次插入和查询时间都是log(C)template<classT>classtrie01{vector<vector<T>>tree;public:trie01():tree(1,vector<T>(2,0)){}//插入待检查的数字voidinsert(Tx){intp=0;for(inti=sizeof......
  • OSG 使用整理(5):模板测试与边缘效果
    osg使用整理(5):模板测试与边缘效果1模板测试​ 在渲染管线中,模板测试在片段着色器后执行,通过像素与模板缓冲中的模板值比较,选择性丢弃或者保存这个像素颜色。我们可以通过更新模板测试来获得一些很有意思的效果。下图为LearnOpenGL网站一个例子。​ 可以发现,颜色缓冲经过模......
  • 15款最佳的HTML5移动模板
    如果你需要响应式和前端开发,那么HTML5是你务必要学会的Web开发语言。我们在Codecondo上发布的HTML5相关文章依然很受欢迎。例如:为HTML5开发者准备的40个工具、针对HTML5的Web框架,你一定要看看它们,我也相信它们会成为你书签的其中之一。当人们上网搜索登陆页面的时候,他们大多是寻......
  • P3378 【模板】二叉堆
    [洛谷]P3378【模板】堆方法一手写堆最小堆插入从新增的最后一个结点的父结点开始,用要插入元素向下过滤上层结点(相当于要插入的元素向上渗透)voidsiftdown(inti)//传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点开始向下调整{intt,flag=0;//flag用来标......
  • 洛谷题解——【模板】堆
    题目链接:【模板】堆【模板】堆题目描述给定一个数列,初始为空,请支持下面三种操作:给定一个整数\(x\),请将\(x\)加入到数列中。输出数列中最小的数。删除数列中最小的数(如果有多个数最小,只删除\(1\)个)。输入格式第一行是一个整数,表示操作的次数\(n\)。接下来\(n\)......
  • C++ 设计模式之模板方法模式
    设计模式之模板方法模式模板方法模式,定义一个操作中的算法的股价,而将一些步骤延迟到了子类中。模板方法使得子类可以不改变一个算法的结构即可重定义该算法的某些特定步骤。说白了就是有一个算法有很多部分,这个算法在基类中已经定义好了。而算法中的各个部分都写成各个成员函......
  • JAVA设计模式之模板模式
    设计模式设计模式(DesignPattern)是前辈们对代码开发经验的总结,是解决特定问题的一系列套路。它不是语法规定,而是一套用来提高代码可复用性、可维护性、可读性、稳健性以及安全性的解决方案。总体来说设计模式分为三大类:创建型模式,共五种:工厂方法模式、抽象工厂模式、单例模式、......
  • 解决Android studio 新建文件固定创建人创建时间模板的具体操作步骤
    AndroidStudio新建文件固定创建人创建时间模板在开发Android应用程序时,我们经常需要创建许多不同类型的文件,例如Activity、Fragment、Adapter等。为了提高开发效率,我们可以在AndroidStudio中使用模板来自动生成这些文件的代码。在本文中,我们将介绍如何在AndroidStudio中创建一......