首页 > 其他分享 >洛谷题单指南-二叉堆与树状数组-P1168 中位数

洛谷题单指南-二叉堆与树状数组-P1168 中位数

时间:2024-11-08 17:19:11浏览次数:1  
标签:q1 大根堆 cnt int 洛谷题 中位数 二叉 小根堆 P1168

原题链接:https://www.luogu.com.cn/problem/P1168

题意解读:中位数就是位于中间的数,前1个数的中位数是第1个,前3个数的中位数是第2个,前5个数的中位数的第3个...以此类推。

所以,此题本质上就是动态维护一组数,每1/3/5...等奇数个取第k小的数,取一次后k++。

解题思路:

要动态维护数据,且每次取第k小的数,又有多种做法:快选、平衡树、双堆,这里依然采用双堆做法:

定义一个小根堆,一个大根堆,确保小根堆的堆顶大于大根堆的堆顶,大根堆的元素个数保持在k-1个,这样每次取小根堆的堆顶即是第k小的数。

本题和P1801 黑匣子本质上是一样的。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
int n, a;
priority_queue<int> q1; //大根堆
priority_queue<int, vector<int>, greater<int>> q2; //小根堆
int cnt;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a;
        q1.push(a);
        if(q1.size() > cnt) //如果大根堆超过cnt个
        {
            q2.push(q1.top()); //将大根堆堆顶移至小根堆
            q1.pop();
        }

        if(i % 2 == 1) //每奇数个
        {
            cout << q2.top() << endl; //输出第cnt+1小的值
            cnt++; //cnt下次+1

            if(q1.size() < cnt) //如果大根堆不足cnt个
            {
                q1.push(q2.top()); //将小根堆堆顶移至大根堆
                q2.pop();
            }
        }
    }
    return 0;
}

 

标签:q1,大根堆,cnt,int,洛谷题,中位数,二叉,小根堆,P1168
From: https://www.cnblogs.com/jcwy/p/18534554

相关文章

  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的intg......
  • 二叉树遍历
    二叉树遍历这个问题,以前一直没搞懂,只是模糊的了解。先序遍历:先访问根节点,再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点,再访问根节点,最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树,再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
  • 代码随想录算法训练营第二十一天| leetcode669. 修剪二叉搜索树、leetcode108.将有序
    1leetcode669.修剪二叉搜索树题目链接:669.修剪二叉搜索树-力扣(LeetCode)文章链接:代码随想录视频链接:你修剪的方式不对,我来给你纠正一下!|LeetCode:669.修剪二叉搜索树_哔哩哔哩_bilibili思路:目前想的是分三种情况,第一种情况就是这个数删除左边全部,第二种删除右边的全部,第......
  • 二叉树 (王道数据结构 C语言版)
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 代码随想录算法训练营第二十天|leetcode235. 二叉搜索树的最近公共祖先、leetcode701.
    1leetcode235.二叉搜索树的最近公共祖先题目链接:235.二叉搜索树的最近公共祖先-力扣(LeetCode)文章链接:代码随想录视频链接:二叉搜索树找祖先就有点不一样了!|235.二叉搜索树的最近公共祖先_哔哩哔哩_bilibili思路:用之前一样的方法,哈哈哈哈哈,好处就是做出来了,但是我觉得需......
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件:写完了递归算法,运行的时......
  • 洛谷题单指南-二叉堆与树状数组-P2827 [NOIP2016 提高组] 蚯蚓
    原题链接:https://www.luogu.com.cn/problem/P2827题意解读:初始n个数,每次取最大值x,根据u/v分成两部分:x*u/v,x-x*u/v,然后其余数都增加q,整个过程重复m次。输出有两类数据:第t,2t,3t...次取出的最大值;最后剩余的数第t,2t,3t...个,从大到小输出。解题思路:直观上,通过模拟法可以实......
  • 验证二叉搜索树
    题目描述给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树。有效二叉搜索树定义如下:节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。98.验证二叉搜索树-力扣(LeetCode) 解题思......
  • 基于信息增益和基尼指数的二叉决策树
    #coding:UTF-8'''基于信息增益和基尼指数的二叉决策树的实现。该决策树可以用于分类问题,通过选择合适的特征来划分样本。'''fromcollectionsimportCounterclassbiTree_node:'''二叉树节点定义每个节点可以是叶子节点或内部节点。'''def_......
  • 华为OD机试真题-数组二叉树码-2024年OD统一考试(E卷)
    最新华为OD机试考点合集:华为OD机试2024年真题题库(E卷+D卷+C卷)_华为od机试题库-CSDN博客     每一题都含有详细的解题思路和代码注释,精编c++、JAVA、Python三种语言解法。帮助每一位考生轻松、高效刷题。订阅后永久可看,发现新题及时跟新。题目描述二叉树也可以用数组来......