[luogu1168]中位数_优先队列
2024-10-13 12:55:39
中位数
题目大意:输出读入的前2*k+1个数的中位数。一共有n个数,按照读入顺序。
注释:$1\le n \le 10^9$。
想法:这是优先队列的一个应用qwq。我们弄两个堆。小根堆和大根堆,保证:大根堆中的任意一个数都小于小根堆,而且大根堆中的元素个数始终比小根堆大且只大1。最后我们只需要输出大根堆的对顶即可。具体地:我们对于每一个新读入的元素和原本合法的大、小根堆进行操作,将当前元素和大根堆对顶进行比较,如果当前元素大于大根堆对顶,我们就将其扔进小根堆,反之,扔进大根堆,显然是正确的。在维护大、小根堆的数目时,我们通过循环处理,无非就是讲大、小根堆的堆顶倒来倒去。
最后,附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int> >q2;
// int a[100100];
int main()
{
int n;
scanf("%d",&n);
int sum_for_Big=0;//大根堆数目
int sum_for_Small=0;//小根堆数目
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
if(i==1)
{
sum_for_Big=1;
q1.push(a);
sum_for_Small=0;
printf("%d\n",a);
}
else
{
if(a<q1.top())//插入元素
{
q1.push(a);
sum_for_Big++;
}
else q2.push(a),sum_for_Small++;
if(i%2==1)
{
while(sum_for_Big-sum_for_Small!=1)//维护大、小根堆的数目关系
{
if(sum_for_Big<sum_for_Small)
{
int x=q2.top();
q2.pop();
sum_for_Small--;
q1.push(x);
sum_for_Big++;
}
else
{
int x=q1.top();
q1.pop();
sum_for_Big--;
q2.push(x);
sum_for_Small++;
}
}
printf("%d\n",q1.top());
}
}
}
// printf("%d %d\n",sum_for_Big,sum_for_Small);
// printf("%d\n",q1.top());
// printf("%d\n",q2.top());
return 0;
}/*
3 1 3 5
*/
小结:priority的应用,好像suika学长说heap比这鬼东西快一万倍... ...
最新文章
- linux桌面环境gnome,kde,xfce,lxde 使用比较(转)
- Javascript中函数的四种调用方式
- iphone 如何清空UIWebView的缓存
- CSS Masking(翻译)
- cdoj 排名表 拓扑排序 排名输出 贪心
- 自定义TWebBrowser浏览器控制遇到的一些问题
- SE 2014 年4月21日(二)
- LeetCode-2 Keys Keyboard
- Cocoa包管理器之CocoaPods详解
- vue项目使用websocket技术
- oracle 行列转换
- asp.net core系列 39 Web 应用Razor 介绍与详细示例
- 添加字体与字符集locale支持(基于busybox文件系统)
- Fiddler抓包域名过滤(转载)
- 使用webstorm创建vue项目
- 解决修改完系统默认python版本后yum不可用的问题!!!!!!
- php中使用static方法
- KMP算法_模板_C++
- sqlserver 事务日志
- 初始化mysql数据库时提示字符编码错误的解决办法
热门文章
- javascript 学习笔记 三大特性
- 嵌入式linux------ffmpeg移植 解码H264(am335x解码H264到yuv420并通过SDL显示)
- TypeError: Error #1034: 强制转换类型失败:无法将 mx.controls::DataGrid@9a7c0a1 转换为 spark.core.IViewport。
- Python中进程
- [HNOI2013]消毒
- [HAOI2010]软件安装
- Bzoj1901 Dynamic Ranking
- Angular和Vue.js 深度对比
- css块级元素和内联元素
- 软件License认证方案的设计思路