【数据结构•堆】经典问题：k路归并

题目描述

k路归并问题：
　　把k个有序表合并成一个有序表。（ k <= 10^4 ）

输入输出格式

输入格式：

　　输入数据共有 2*k+1 行。
　　第一行，一个整数k（ k <= 10^4 ），表示有k个有序表（均为从小至大有序）。
　　从第2行开始，接下来共有2*k行，第 2*(i-1)+2 行为一个整数ni（ ni <= 100 ），第 2*(i-1)+3 行共有ni个整数，每个整数均小于2^31。（ 1 <= i <= k ）

输出格式：

　　输出数据一行，合并后的有序表（从小至大排序，每个整数之间有一个空格）。

提示信息

数据范围：
　　30%数据：k <= 10
　　50%数据：k <= 100
　　70%数据：k <= 1000
　　100%数据：k <= 10000，ni <= 100

算法分析：

最裸题目

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > p;
int main()
{int k;cin>>k;for(int i=1;i<=k;i++){int n;cin>>n;for(int j=1;j<=n;j++){int x;cin>>x;p.push(x);}}while(!p.empty()){cout<<p.top()<<" ";p.pop();}return 0;
}