題目：
依次讀入一個整數序列，每當已經讀入的整數個數為奇數時，輸出已讀入的整數構成的序列的中位數，
輸入格式
第一行輸入一個整數P，代表后面資料集的個數，接下來若干行輸入各個資料集，
每個資料集的第一行首先輸入一個代表資料集的編號的整數，
然后輸入一個整數M，代表資料集中包含資料的個數，M一定為奇數，資料之間用空格隔開，
資料集的剩余行由資料集的資料構成，每行包含10個資料，最后一行資料量可能少于10個，資料之間用空格隔開，
輸出格式
對于每個資料集，第一行輸出兩個整數，分別代表資料集的編號以及輸出中位數的個數（應為資料個數加一的二分之一），資料之間用空格隔開，
資料集的剩余行由輸出的中位數構成，每行包含10個資料，最后一行資料量可能少于10個，資料之間用空格隔開，
輸出中不應該存在空行，
資料范圍
1≤P≤1000,
1≤M≤9999
輸入樣例：
3
1 9
1 2 3 4 5 6 7 8 9
2 9
9 8 7 6 5 4 3 2 1
3 23
23 41 13 22 -3 24 -31 -11 -8 -7
3 5 103 211 -311 -45 -67 -73 -81 -99
-33 24 56
輸出樣例：
1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3
-7 -3
解題思路：
使用“對頂堆”演算法
使用一個大根堆和一個小根堆，將小于中位數的部分都放在大根堆（以便訪問堆中最大值），大于中位數的部分都放在小根堆里（以便取出堆中最小值），保證大根堆中的元素個數始終比小根堆中的元素個數多1，那么我們所需要的答案即為大根堆的堆頂元素，
在這里使用STL優先佇列來實作小根堆和大根堆，
代碼
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
priority_queue<int>dgd;//大根堆
priority_queue<int,vector<int>,greater<int> >xgd;//小根堆
int main()
{
int p,m,count;
scanf("%d",&p);
while(p--)
{
while(dgd.size())
dgd.pop();//清空
while(xgd.size())
xgd.pop();//清空
int x,cnt=0;
scanf("%d%d",&count,&m);
printf("%d %d\n",count,m/2+1);
for(int i=0;i<m;i++)
{
scanf("%d",&x);
if(xgd.empty())
xgd.push(x);
else
{
if(x>xgd.top())
xgd.push(x);
else
dgd.push(x);
while(xgd.size()<dgd.size())
{
xgd.push(dgd.top());
dgd.pop();
}
while(xgd.size()>dgd.size()+1)
{
dgd.push(xgd.top());
xgd.pop();
}
}
if((i+1)&1)
{
cnt++;
printf("%d ",xgd.top());
if(!(cnt%10))
printf("\n");
}
}
printf("\n");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/138803.html
標籤：其他
上一篇：數論篇5——數論四大定理