【Luogu1631】序列合并（优先队列）

problem

• 两个长为n的序列A,B。保证AB已升序排序。
• 在AB中各任取一个值相加得到N^2 个数。求其中最小的N个数
• n < 1e5

solution

• 很显然暴力枚举O(n^2)过不了。考虑题设中最后一个条件是已升序排序。

众所周知，最小的数字就是a[1]+b[1]
那么第二个数字一定是a[1]+b[2]、a[2]+b[1]中的一个！

所以设当前最小的是a[l]+b[r]
那么下一个答案就存在于a[l+1]+b[r]和a[l]+b[r+1]中。

所以我们搞个优先队列，每次取出最小的输出，并对它进行扩展。
记得判重（数组会炸空间，所以set[l]表示l已经和哪些数组合过了）。
复杂度O(nlogn).

codes

#include<iostream>
#include<queue>
#include<set>
using namespace std;
const int maxn = 1e5+10;

int n, a[maxn], b[maxn];

struct node{int l, r;};
bool operator < (node x, node y){return a[x.l]+b[x.r]>a[y.l]+b[y.r];}
priority_queue<node,vector<node>,less<node> >q;

set<int>s[maxn];

int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 1; i <= n; i++)cin>>a[i];
    for(int i = 1; i <= n; i++)cin>>b[i];
    q.push(node{1,1});
    for(int i = 1; i <= n; i++){
        node t = q.top();  q.pop();
        cout<<(a[t.l]+b[t.r])<<' ';
        if(t.l+1<=n && !s[t.l+1].count(t.r))
            q.push(node{t.l+1,t.r}), s[t.l+1].insert(t.r);
        if(t.r+1<=n && !s[t.l].count(t.r+1))
            q.push(node{t.l,t.r+1}), s[t.l].insert(t.r+1);
    }
    return 0;
}
  
 

  
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
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/81561214