题目链接
题意：
有两个长度都为N(1<=N<=100000)的序列A和B，在A和B中各取一个数相加可以得到N2个和，求这N2个和中最小的N个。
思路：
首先会想到暴力，O(N^2)，一看范围十万，肯定受不了。
再考虑贪心，以两个队列的头相加，进入前n小的和中，然后选择两头中较大的元素弹出，以此类推，但我发现一个问题：虽然这样所找出的元素满足单调递增，但每个被弹出的元素在弹出后就不用了，将会导致的情况我用一个样例来表示：
5
2 4 9 10 11
1 1 1 1 1
答案显然是3 3 3 3 3,然而贪心给出的是3 5 10 11 11。
考虑记忆化搜索和dp，但记忆化的f存什么呢？存第n个最小的和吗？但我们还不知道第n小的和的值，存当前已知的数值吗？显然不行。dp似乎行得通，dp通常用于最优性问题，但我没想出来。
我发现题目中有：Ai<=A{i+1}，Bi<=B{i+!}。那么可以得出：
[A_i+B_ile A_{i+1}+B_i,A_i+B_{i+1}
]
所以每得到一个和n=Ai+Bi，那么就将Ai+1和Bi的和与Ai和Bi+1的和放入某个容器，而这个容器中的最小者定为下一个最小的（想想为什么?）。
那么既然是堆的题，又是求最小者，那么这个容器的最佳候选者应当是小根堆，堆的插入、删除操作都只有O(log2(n))的复杂度，要找n个最小和，就是O(nlog2(n))的复杂度，可以承受。
100分AC代码
#include <bits/stdc++.h>
using namespace std;
int n,cnt=0;
int a[100005];
int b[100005];
struct node{
int a;
int b;
int num;
}heap[200005];
map<int,map<int,int> > mapp;//防止重复计算相当于bool b[ai][bi]，但这样会爆
void upd(int now){
if(now>cnt)return ;
int j=now*2;
if(heap[j].num>heap[j+1].num){
j+=1;
}
if(heap[j].num<heap[now].num&&j<=cnt){
swap(heap[now],heap[j]);
upd(j);
}
return ;
}
void deltop(){
heap[1].num=heap[cnt].num;
heap[1].a=heap[cnt].a;
heap[1].b=heap[cnt].b;
cnt--;
upd(1);
}
void dwd(int now){
if(now==1)return ;
int f=now>>1;
if(heap[f].num>heap[now].num){
swap(heap[f],heap[now]);
dwd(f);
}
return ;
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++)cin>>b[i];
heap[++cnt].num=a[1]+b[1];
heap[cnt].a=1;
heap[cnt].b=1;
mapp[1][1]=1;
for(int t=1;t<=n;t++){
cout<<heap[1].num<<' ';
int aa=heap[1].a,bb=heap[1].b;
if(!mapp[aa+1][bb]){
mapp[aa+1][bb]=1;
++cnt;
heap[cnt].num=a[aa+1]+b[bb];
heap[cnt].a=aa+1;
heap[cnt].b=bb;
dwd(cnt);
}
if(!mapp[aa][bb+1]){
mapp[aa][bb+1]=1;
++cnt;
heap[cnt].num=a[aa]+b[bb+1];
heap[cnt].a=aa;
heap[cnt].b=bb+1;
dwd(cnt);
}
deltop();
}
return 0;
}
大功告成！