题目描述
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N2个和，求这N2个和中最小的N个。
输入输出格式
输入格式：
第一行一个正整数N；
第二行N个整数Ai?, 满足Ai?≤Ai+1?且Ai?≤109;
第三行N个整数Bi?, 满足Bi?≤Bi+1?且Bi?≤109.
输出格式：
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入输出样例
输入样例#1： 复制
3 2 6 6 1 4 8
输出样例#1： 复制
3 6 7
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
如何在朴素做法$n^2$之上进行优化？我们每次都是要取出当前最小的两个数进行合并。由于原序列是有序的，$a[1]$是一定会被取到的。假设我们当前取出的是$a[i]+b[j]$，那么我们下一次取的就是$a[i]+b[j+1]$或$a[i+1]+b[j]$。我们先把$b$序列中所有数与$a[1]$的和放入优先队列，这样就满足了$a[i]+b[j+1]$的情况。（因为$a[1]$一定比$a$数组后面的优
所以重点就是处理$a[i+1]+b[j]$，每次把取出$b[j]$对应的取到$a$数组中的位置往后移一个加入队列即可。
【注意】优先队列套$pair$是默认按第一个元素从大到小排序。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int n, a[100005], b[100005], to[100005]; priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > q; int main ( ) { scanf ( "%d", &n ); for ( int i = 1; i <= n; i ++ ) scanf ( "%d", &a[i] ); for ( int i = 1; i <= n; i ++ ) { scanf ( "%d", &b[i] ); q.push ( make_pair ( b[i] + a[1], i ) ); to[i] = 1; } for ( int i = 1; i <= n; i ++ ) { printf ( "%d ", q.top ( ).first ); int j = q.top ( ).second; q.pop ( ); q.push ( make_pair ( b[j] + a[++to[j]], j ) ); } return 0; }