当前位置: 首页 > article >正文

AcWing 5960:输出前k大的数 ← 小根堆

【题目来源】
https://www.acwing.com/problem/content/5963/

【题目描述】
给定一个长度为 n 的数组 a1,a2,…,an,统计前 k 大的数并且把这 k 个数从大到小输出。

【输入格式】
第一行包含整数 n。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含整数 k。​​​​​​​

【输出格式】
从大到小输出前 k 大的数,每个数一行。

【数据范围】
1≤n≤10^5,
−10^9≤ai≤10^9,
1≤k≤n

【输入样例】
10
4 5 6 9 8 7 1 2 3 0
5​​​​​​​

【输出样例】
9
8
7
6
5

【算法分析】
● 
vector<int> arr(n); 是创建了一个包含n个int元素的vector,每个元素会被默认初始化为0。

【算法代码】

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

priority_queue<int, vector<int>, greater<int>> L; //小根堆
priority_queue<int> G; //大根堆

int main() {
    int n,k;
    cin>>n;

    vector<int> arr(n);
    for(int i=0; i<n; i++) {
        cin>>arr[i];
    }
    cin>>k;

    for(int x:arr) {
        if(L.size()<k) L.push(x);
        else if(x>L.top()) {
            L.pop();
            L.push(x);
        }
    }

    while(!L.empty()) {
        G.push(L.top());
        L.pop();
    }

    while(!G.empty()) {
        cout<<G.top()<<endl;
        G.pop();
    }

    return 0;
}

/*
in:
10
4 5 6 9 8 7 1 2 3 0
5

out:
9
8
7
6
5
*/



【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/119813940
https://blog.csdn.net/hnjzsyjyj/article/details/146315528
https://www.acwing.com/solution/content/258025/




 


http://www.kler.cn/a/589471.html

相关文章:

  • 快速方便的Docker下载,包含Win、Mac
  • 汇编基础知识
  • 东方通TongHttpServer:企业级服务代理中间件的卓越之选
  • 泛型主要是用于静态类型检查的工具,它并不会在运行时自动验证返回值类型和传入类型是否一致
  • Linux驱动学习笔记(二)
  • Androidstudio实现一个app引导页(超详细)
  • 三维重建(十七)——obj文件解读+ply文件解读
  • C++ 位图 bitset
  • 使用 netstat 和 tasklist 命令排查端口占用问题
  • 解决前端文字超高度有滚动条的情况下padding失效(el-scrollbar)使用
  • 【愚公系列】《高效使用DeepSeek》012-合同文档合规性检查
  • spring中将yaml文件转换为Properties
  • 【Kubernetes】Kubernetes 如何进行容器编排和调度?如何使用 kubectl`创建和管理 Pod、Deployment、Service?
  • 51单片机指令系统入门
  • 国产编辑器EverEdit - 命令窗口的使用
  • CRTP奇异递归模板模式
  • SSM框架——Spring面试题
  • 因果推荐|可解释推荐系统的反事实语言推理
  • Spring Boot 整合 Elasticsearch:打造高性能全文检索实战
  • Mac电脑python 有没有ros接口 查看lidar的数据