【题目描述】

k路归并问题
把k个有序表合并成一个有序表。
元素共有n个。

【输入描述】

读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数，表示第i个序列。
总数小于100000。

【输出描述】

【样例输入】

6
3 1 2 3
3 4 5 6
3 7 10 13
3 8 11 14
3 9 12 15
3 0 16 17

【样例输出】

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

【题目分析】

核心方法

1. 把所有数字全部存到一个大数组里（不管顺序）。

2. 直接对整个大数组排序（sort）。

3. 输出排序后的结果。

为什么可以这样做？

• 题目已经告诉我们 每个子数组都是有序的，但 合并后的数组不一定有序。

• 直接 全部存到一个数组里再排序，是最简单的方法（但效率不是最高）。

例子：

3
3 1 5 9
2 2 6
4 3 4 7 8

执行过程

1. 读取输入：

• K=3（3 个子数组）。

• 第1个子数组：[1, 5, 9]（长度 3）。

• 第2个子数组：[2, 6]（长度 2）。

• 第3个子数组：[3, 4, 7, 8]（长度 4）。

2. 合并到 result：

• result = [1, 5, 9, 2, 6, 3, 4, 7, 8]（共 9 个数字）。

3. 排序 result：

• std::sort → [1, 2, 3, 4, 5, 6, 7, 8, 9]。

4. 输出：

• 1 2 3 4 5 6 7 8 9。

【参考答案】

#include <iostream>
#include <algorithm>
using namespace std;
int lists[100][100];//存储所有子数组
int sizes[1000]; //每个子数组的长度（大小） 
int result[1000]; //存放最终合并后的数组
int total_size; //合并后数组总长度 
void mergeKSortedLists(int K) {
    total_size = 0; 
    // 将所有子序列的元素存入 result
    for (int i = 0; i < K; i++) {
        for (int j = 0; j < sizes[i]; j++) {
            result[total_size++] = lists[i][j];  //把 lists[i][j] 的值存入 result，并让 total_size 指向下一个位置。
        }
    }
    // 直接排序
    sort(result, result + total_size);
}

int main() {
    int K;
    cin >> K;

    // 读取输入
    for (int i = 0; i < K; i++) {
        cin >> sizes[i];
        for (int j = 0; j < sizes[i]; j++) {
            cin >> lists[i][j];
        }
    }
	//调用函数 
    mergeKSortedLists(K);
    // 输出结果
    for (int i = 0; i < total_size; i++) {
        cout << result[i] << " ";
    }
    cout << endl;
    return 0;
}

注：很难拿到满分

【思路二】：直接使用优先队列

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int,vector<int>,greater<int> >q;
	int n,x,y,i,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>x;
		for(j=1;j<=x;j++)
		{
			cin>>y;
			q.push(y);
		}
	}
	while(!q.empty()) 
	{
		cout<<q.top()<<endl;
		q.pop();
	}
	return 0;
}