【题目描述】

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;  }