首先对于两个序列$a,b$最小的肯定是$a_1+b_1$，而次小的就有两种可能$min(a_1+b_2,a_2+b_1)$，假如现在次小是$a_1+b_2$，那么最小的比他大的数就是$min(a_1+b_3,a_2+b_2)$，再与之前的$a_2+b_1$一起更新第三小的值。
由此我们可以发现可以用优先队列来维护最小值，先把二元组$(1,1)$压入，在取出当前值$(x,y)$的时侯这个值对后面的答案产生了贡献$(x+1,y)$和$(x,y+1)$，我们便把他们一起压入，循环$n$次我们就得到了前$n$小的值。
但是我们又发现$(x,y+1)$和$(x+1,y)$可能产生$(x+1,y+1)$这样情况相同，可以用$map$进行判重，这样就可以做出来了
这道题还可以拓展为有$m$个序列的情况（poj2442）其实是一样处理，先处理两个序列得到前$n$小的值把他当作一个新的序列，再和序列$c d e...$进行相同的操作便可以得到答案
另外由于优先队列默认是大根堆排序，所以在重载小于号时候是反着来的。
AC代码：
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
31
32
33
34
35
36
37
38
39
40
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;
typedef pair<int,int> pp;
inline int read()
{
int x=0,t=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*t;
}
int n,a[maxn],b[maxn];
map<pp,int> p;
struct node{
int x,y;
bool operator<(const node&t) const
{
if(a[x]+b[y]<a[t.x]+b[t.y]) return false;
return true;
}
node(int X,int Y){x=X,y=Y;}
};
priority_queue<node> q;
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=n;i++) b[i]=read();
q.push(node(1,1));
for(int i=1;i<=n;i++)
{
while(p[make_pair(q.top().x,q.top().y)]) q.pop();
int xx=q.top().x,yy=q.top().y;
printf("%d ",a[xx]+b[yy]);
p[make_pair(xx,yy)]=1;
q.push(node(xx+1,yy));
q.push(node(xx,yy+1));
}
return 0;
}
|