序列合并-优先队列

题目来源：洛谷 P1631 序列合并&&NEFU OJ-1689 序列合并（后者链接已补，接下来题目描述来自后者，代码符合后者要求）

题目描述

给出两个长度为 n 的有序表 A 和 B，在 A 和 B 中各任取一个元素，可以得到 n^ 2 个和，求这些和中最小的 n 个。

输入描述

第 1 行包含 1 个整数 n（1≤n≤400000）。
第 2 行与第 3 行分别有 n 个整数，各代表有序表 A 和 B。一行中的每两个整数之间用一个空格隔开，大小在长整型范围内，数据保证有序表单调递增。
建议用scanf()读入，否则会TLE!

输出描述

输出共 n 行，每行一个整数，第 i 行为第 i 小的和。
数据保证在 long long 范围内。

输入样例

3
2 6 6
1 4 8

输出样例

3
6
7

OP

先说说优先队列吧：

优先队列，顾名思义就是依照优先程度排列的序列。

如果需要从小到大排序时，与set的表象区别就是set会自动去重，priority_queue 则不会。
如果不计时间复杂度的话，struct 结构体与带 cmp 的 sort 搭配也能达到同样的效果。

思路

首先 O(n²) 妥妥的会爆。

我们要输出前 n 小的数，可以采取边输出边维护的大体方向，同时也要“兼顾”到所有的 n² 项。

对于有序的 A B 数组，我们易知 a[ i ] + b[ j ] 一定小于等于 a[ i ] + b[ j + 1 ]（ 调换 a,b 同理），所以我们可以先将 a[ i ] + b[ 1 ] 全部入队，此时队首元素一定是 a[ 1 ] + b[ 1 ] ，将其出队后，入队 a[ 1 ] + b[ 2 ]。

在接下来的过程中，如果 a[ i ] + b[ j ] 为最小值被出队，就应入队 a[ i ] + b[ j + 1 ] ^{[^1]}，再进行排序（性质）。

对于这个过程，我们可以理解为 对于每一个 i ，都存在一个数组，是 a[ i ] 依次与每一个 b 集合元素的和。对于这一个数组，只有前面的数入队后被出队时，后续元素才有可能入队。
通过此过程，我们就可以在不计算每一个值的情况下，“兼顾”到每一个值。

[^1]：因为总共只需输出 n 个值，所以不需要考虑数组溢出问题。

Q&A

Q：能不能用双指针同时滑动两个数组？
A：这样样例过不去的，可以自己分析一下。大体上就是在滑动过程中，略过了一些可行的值。

代码

#include <bits/stdc++.h>
using namespace std;

struct ord
{
    long long a,na,nb;//na,nb 分别存储 a 对应在数组 A,B 的序号值
};//分号！
priority_queue<ord> qu;
bool operator < (const ord &a,const ord &b)
{
    return a.a >b.a ;
}

long long n,i,j,a[400005],b[400005],c,k,p[400005]= {0};
int main()
{
    scanf("%lld",&n);
    for(i=1; i<=n; i++)scanf("%lld",&a[i]);
    for(i=1; i<=n; i++)scanf("%lld",&b[i]);
    for(i=1; i<=n; i++)qu.push({a[i]+b[1],i,1});
    while(n--)
    {
        printf("%lld\n",qu.top().a);
        qu.push({a[qu.top().na]+b[qu.top().nb+1],qu.top().na,qu.top().nb+1});//A序号值不变，B序号值加一
        qu.pop();
    }
    return 0;
}

ED

想了想，最后归进了DP，感觉思路有些类似吧