两序列前n小的两数和
- 描述：有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到$N^2$个和，求这$N^2$个和中最小的N个。
- 输入：
第一行输入一个正整数N，$1 \le N \le 100000$，表示序列长度；
第二行输入N个整数$A_i$，满足$A_i \le A_{i+1}$且$A_i \le 10^9$；
第二行输入N个整数$B_i$，满足$B_i \le B_{i+1}$且$B_i \le 10^9$。
- 输出：
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
- 样例输入：
3
2 6 6
1 4 8
- 样例输出：
3 6 7
- 解题思路：
由题意可得A和B是两个升序排列的序列，其中：
A[1]+B[1] <= A[2]+B[1] <= … <= A[N]+B[1]
A[1]+B[2] <= A[2]+B[2] <= … <= A[N]+B[2]
……
A[1]+B[N] <= A[2]+B[N] <= … <= A[N]+B[N]
接下来，就相当于要将这N个有序队列进行合并排序：
首先，将这N个队列中的第一个元素放入一个堆中；
然后；每次取出堆中的最小值。若这个最小值来自于第k个队列，那么，就将第k个队列的下一个元素放入堆中。
时间复杂度：O(NlogN)。
堆可用优先队列实现，此题需要的是一个小顶堆。
- 参考代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30#include <cstdio>
#include <queue>
using namespace std;
const int N=1e5+10;
typedef pair<int,int> PII;
int n;
int a[N],b[N],next_of_a[N];
int i;
int main()
{
priority_queue<PII,vector<PII>,greater<PII> > pq;//小顶堆
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
{
scanf("%d",&b[i]);
next_of_a[i]=2;
pq.push({a[1]+b[i],i});
}
while(n--)
{
printf("%d ",pq.top().first);
i=pq.top().second;
pq.pop();
pq.push({a[next_of_a[i]++]+b[i],i});
}
return 0;
}