有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到 N2个和，求这 N2个和中最小的N个。
输入格式：
第一行一个正整数N；
第二行N个整数 Ai? , 满足 Ai≤Ai+1 且 Ai≤109 ;
第三行N个整数 Bi? , 满足 Bi≤Bi+1 且 Bi≤109 .
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
输出格式：
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入样例#1：
3 2 6 6 1 4 8
输出样例#1：
3 6 7
一句话题意: 两个长度为n的单调递增的序列可以组成n2个组合,问这些组合中最小的前n个.
题解:
首先看一下下面这张表:
A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N]
A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N]
……
A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N]
显然,在同一列中，每一行都比上面一行的值要大.
所以,我们可以先将A1~An与B1的值都加入堆中,每次取出了堆中的最小值,就把它所在的行的下一个加入堆中,可以保证这样是单调的.
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100000+5; 4 5 int n, a[N], b[N], ans[N]; 6 7 struct number{ 8 int id1, id2, val; 9 bool operator < (const number &a) const{ 10 return val > a.val; 11 } 12 }; 13 14 priority_queue <number> h; 15 16 int main(){ 17 ios::sync_with_stdio(false); 18 cin >> n; 19 for(int i=1;i<=n;i++) cin >> a[i]; 20 for(int i=1;i<=n;i++) cin >> b[i]; 21 for(int i=1;i<=n;i++) h.push((number){ i, 1, a[i]+b[1] }); 22 for(int i=1;i<=n;i++){ 23 number top = h.top(); h.pop(); 24 ans[i] = top.val; 25 h.push((number){ top.id1, top.id2+1, a[top.id1]+b[top.id2+1] }); 26 } 27 for(int i=1;i<=n;i++) cout << ans[i] << ‘ ‘; cout << endl; 28 return 0; 29 }
-
原文：https://www.cnblogs.com/jiamian/p/11176494.html