poj3784（对顶堆or链表+hash）

我不是女神ヾ 2021-10-18 11:20 273阅读 0赞

## 题意：给出n个数，求出前i个数的中位数(i<n并且i是奇数)。 ##

## 分析：对顶堆板子题，也可以用链表+hash做，不过比较复杂，详见《算法竞赛进阶指南》P36。 ##

## 代码： ##

#include<stdio.h>
    #include<queue>
    using namespace std;
    int t,n,m,u,mid,cas;
    
    /*
    用最大堆维护比当前中位数小的，用最小堆
    维护比当前中位数大的，如果两个堆大小差
    为2，则将中位数加入大小较小的堆，并且
    将另一个堆的顶作为新的中位数
    */
    
    int main(){
        scanf("%d",&t);
        while(t--){
            priority_queue<int> qu;
            priority_queue<int,vector<int>,greater<int> >qu1;
            scanf("%d%d",&n,&m);
            printf("%d %d\n",n,(m+1)/2);
            for(int i=1;i<=m;i++){
                scanf("%d",&u);
                if(i==1){
                    cas=1,mid=u;
                    printf("%d ",mid);
                    continue;
                }
                if(u<mid) qu.push(u);
                else qu1.push(u);                   
                if(qu.size()-qu1.size()==2){
                    qu1.push(mid);                  
                    mid=qu.top();                 
                    qu.pop();
                }
                else if(qu1.size()-qu.size()==2){
                    qu.push(mid);
                    mid=qu1.top();
                    qu1.pop();
                }
                if(i%2!=0){
                    cas++;
                    if(cas%10==0) printf("%d\n",mid);
                    else printf("%d ",mid);
                }
            }
            if(cas%10!=0) printf("\n");
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，273人围观）

还没有评论，来说两句吧...

相关阅读

相关封装对顶堆板子

不懂，这都能称为板子吗无所谓，下午太闲随便写的，已经靠这个水掉好几道洛谷了嘻嘻参考的是这个： ![5b330d47f8809ced9530ff398a8d4af5.p

Dear 丶/ 2024年03月29日 16:21/ 0 赞/ 70 阅读

相关对顶堆模板！！【DS对顶堆】ABC281 E - Least Elements

我想的思路和正解是差不多的就是滑动窗口，每过去一个用DS维护一下前k个元素和sum 本来想的是用优先队列维护前k个然后想着multiset维护前k个，但是具体不知道怎

￡神魔★判官ぃ/ 2024年03月22日 10:42/ 0 赞/ 83 阅读

相关学习：堆排序（大顶堆）

学习：堆排序（大顶堆） include <iostream> include <cassert> include <ctime> incl

阳光穿透心脏的1/2处/ 2023年03月13日 02:19/ 0 赞/ 25 阅读

相关 hash表-使用数组加链表实现hash表

hash表-使用数组加链表实现hash表 hash.h typedef int ElementType; struct ListNode{

深碍√TFBOYSˉ_/ 2022年10月07日 06:59/ 0 赞/ 156 阅读

相关 poj 3349（hash）

很久就听说过hash了，但是一直没有做过相关的题目。题意大概就是给你n个雪花，每个雪花有六个花瓣代表六个值，判断是否有至少一对相同的雪花。由于n值较大，而且每次要判断6

不念不忘少年蓝@/ 2022年08月25日 11:58/ 0 赞/ 15 阅读

相关堆排序之大顶堆

对于具有n个元素的序列，采用堆积排序方法需要进行n-1趟排序才能达到目的 include <stdio.h> void ADJUST(int a[],int

╰半橙微兮°/ 2022年05月09日 09:58/ 0 赞/ 229 阅读

相关 HDOJ 3784

继续xxx定律 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe

￡神魔★判官ぃ/ 2022年04月10日 14:09/ 0 赞/ 168 阅读

相关 POJ 3253 Fence Repair(小顶堆的应用)

Fence Repair <table> <tbody> <tr> <td> <p><strong>Time Limit:</strong> 20

忘是亡心i/ 2021年11月02日 06:32/ 0 赞/ 225 阅读

相关 poj3784（对顶堆or链表+hash）

题意：给出n个数，求出前i个数的中位数(i<n并且i是奇数)。分析：对顶堆板子题，也可以用链表+hash做，不过比较复杂，详见《算法竞赛进阶指南》P36。代码

我不是女神ヾ/ 2021年10月18日 11:20/ 0 赞/ 274 阅读

相关堆排序（大顶堆、小顶堆）----C语言

堆排序之前的随笔写了栈（[顺序栈][Link 1]、[链式栈][Link 2]）、队列（[循环队列][Link 3]、[链式队列][Link 4]）、[链表][Link

小鱼儿/ 2021年06月10日 20:38/ 0 赞/ 511 阅读