正经向-蓝桥杯：N个最小和
难得的正经向题解系列，如果想要补充基础知识+AC题解的话请移步：备战CCC-优先队列还行【蓝桥杯-N个最小和】
题面
给出两个包含 n 个整数的数组 A，B。分别在 A, B 中任意出一个数并且相加，可以得到 n^2个和。求这些和中最小的 n 个。
输入格式 输入第一行一个整数n(1≤n≤50000)。接下来一行输入数组 A，用空格隔开。接下来一行输入数组 B，用空格隔开。1<=ai<=10^9.
输出格式 从小到大输出最小的 n 个和，用空格隔开。
样例输入 4 1 3 5 7 2 4 6 8
样例输出 3 5 5 7
变态思路
首先排除暴力排序之类的，因为时间复杂度爆炸肯定不行，
假设现在这两列的数字都是被从小到大排好序的，
然后把A1与每一个B中的数字分别相加，得到一个数列，因为B也是从小到大排序的，所以我们就可以得出：
A1+B1≤A1+B2≤A1+B3≤......【最小相加和最小】
同理把A2也一样如上操作，我们也可以得到：
A2+B1≤A2+B2≤A2+B3≤......
对A中的的N的数进行操作，我们就会得到N个这样的数列，关系如下：
image
现在我们知道，任何一个表前面的第一组肯定是这个表中最小的和，那我们为什么不创建这样一个结构，每次我们弹出这个结构中和最小的组合（比如A1+B1），取而代之的是当前表中的下一个组合，比如A1+B2
而这个结构中的总长度是永远都不会变的，因为每当一个组合被弹出，都会有一个在属于它的表中比它大的组合补充进来。
现在我们只需要一种“自然”的就可以筛选出最小和的容器，找到这种容器我们剩下的就只是不断的按回车了【暴论】
不约而同的肯定就是优先数组了，因为处在优先数组top处的数据总是最小的【你可以修改优先级啊】
操作步骤：
1.把所有表的最左边推入优先队列，也就是A1-n +B1的组合，一共有n-1个和，
2.这时候我们只需要通过修改运算符让和小的优先度高，我们再弹出队列顶端的元素就行【因为队列顶端的肯定是最小的呀，优先队列嘛~】
3.现在因为刚刚那个表最小的一个已经被我们用掉了啦，我们现在就把刚刚那个表的左边第二个给放入队列中，保证嗦现在当前表中出了被我们弹出的组合之外其他的都放入队列中了
4.循环上面操作n次即可，
因为每一次弹出过后都会有一个新的元素被加入进来，所以优先队列的长度应该一直都是n
代码讲解
1.首先我创建了一种名叫node1的结构体，在结构体中储存着三种变量：
- id1-第一个数字在A中的下标位置
- id2-第二个数字在B中的下标位置
- num-两个数字的和
然后进行了运算符重载，目的是为了在优先队列中使得num小的优先级别高，从而排在队列的顶端。
struct node{
int id1=0,id2=0,num=0;
bool operator<(const node &rhs) const
{
return num>rhs.num;
}
};
priority_queue<node> pq;
最后就是创建了一个以node为数据类型的优先列表了pq了。【记住queue这种数据结构是不能通过下标和迭代器访问的哦，只有队列顶部和队列尾部来进行访问的哦】
2.这一点的sort非常重要，对应的就是上文的把A和B从小到大排序了，如果没有这一步的话整个算法的基础也就不存在，因为要输出最小的N个和嘛qwq
int n;
cin>>n;
int A[n],B[n];
for(int i=0;i<n;i++)
{
nt num;
cin>>num;
A[i]=num;
}
for(int i=0;i<n;i++)
{
int num;
cin>>num;
B[i]=num;
}
sort(A,A+n);
sort(B,B+n);
3.根据我们刚刚排序的A和B两个数组，我们就可以开始初始化了， 初始化的时候，将(A[i]+B[1],i,1)推入优先队列，一共有n个，
这里嗦一下为什么不能用两个优先队列A和B，我之前的傻掉了跑去写了两个优先队列A和B，如果使用了优先队列的话 那么id什么的还有用嘛qwq【都说了queue没有下标这种东西了】
for(int i=0;i<n;i++)
{
node temp;
temp.num=A[i]+B[0];
temp.id1=i;
temp.id2=0;
pq.push(temp);
}
4.接着从结构顶部取出当前最小的一个node，sum拿去输出，把(A[node.id1]+B[node.id2],id1,id2+1)再次推入优先队列中，整个过程中优先队列的总长度是不变的，都是n，时间复杂度是logn，比暴力不知道高到哪里去了，
循环以上操作n次，就取到了n个最小的值了~
for(int i=0;i<n;i++)
{
node now=pq.top();
node temp;
pq.pop();
cout<<now.num;
if(i!=n-1)
{
cout<<" ";
}
temp.id1=now.id1;
temp.id2=now.id2+1;
temp.num=A[now.id1]+B[now.id2+1];
pq.push(temp);
}
AC代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int id1=0,id2=0,num=0;
bool operator<(const node &rhs) const
{
return num>rhs.num;
}
};
priority_queue<node> pq;
int main()
{
int n;
cin>>n;
int A[n],B[n];
for(int i=0;i<n;i++)
{
int num;
cin>>num;
A[i]=num;
}
for(int i=0;i<n;i++)
{
int num;
cin>>num;
B[i]=num;
}
sort(A,A+n);
sort(B,B+n);
for(int i=0;i<n;i++)
{
node temp;
temp.num=A[i]+B[0];
temp.id1=i;
temp.id2=0;
pq.push(temp);
}
for(int i=0;i<n;i++)
{
node now=pq.top();
node temp;
pq.pop();
cout<<now.num;
if(i!=n-1)
{
cout<<" ";
}
temp.id1=now.id1;
temp.id2=now.id2+1;
temp.num=A[now.id1]+B[now.id2+1];
pq.push(temp);
}
return 0;
}
