正文
洛谷 P1631 序列合并(优先队列)
小程序:扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
【扫一扫了解最新限行尾号】
复制小程序
传送门
解题思路
首先读入a、b数组后,sort一遍(从小到大),然后把a[1]+b[1],a[2]+b[1],a[3]+b[1]……a[n]+b[1]全部加入一个优先队列q(小根堆)。
然后从一到n循环,每一次取出队列中的最小的元素(假设是a[i]+b[j]),输出数值,然后把数值修改为a[i]+b[j+1],存入队列。
为什么呢?
很显然,我们把所有可能的情况列成一张表:
a[1]+b[1],a[2]+b[1],a[3]+b[1],……,a[n]+b[1];
a[1]+b[2],a[2]+b[2],a[3]+b[2],……,a[n]+b[2];
…………………………………………………………;
a[1]+b[n],a[2]+b[n],a[3]+b[n],……,a[n]+b[n]。
很显然,在这张表中,对于每一个数都一定小于它右下方的所有的数。
换一种说法,就是在第[i,j]个数为成为当前最小值时,它右下方的数不可能成为当前最小值。
所以只有在第[i,j]个数成为当前最小值时,把第[i+1][j]加入队列,继续比较。(也就是纵向更新)。
AC代码
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=;
int n,a[maxn],b[maxn];
struct node{
int ans,bb;
bool operator < (const node &x)const{
return ans>x.ans;
}
};
priority_queue<node> q;
int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) cin>>b[i];
sort(a+,a+n+);
sort(b+,b+n+);
for(int i=;i<=n;i++){
node x;
x.ans=a[i]+b[];
x.bb=;
q.push(x);
}
for(int i=;i<=n;i++){
node now=q.top();
q.pop();
cout<<now.ans<<" ";
now.bb++;
now.ans=now.ans+b[now.bb]-b[now.bb-];
q.push(now);
}
return ;
}
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=;
int n,a[maxn],b[maxn];
struct node{
int ans,bb;
bool operator < (const node &x)const{
return ans>x.ans;
}
};
priority_queue<node> q;
int main()
{
cin>>n;
for(int i=;i<=n;i++) cin>>a[i];
for(int i=;i<=n;i++) cin>>b[i];
sort(a+,a+n+);
sort(b+,b+n+);
for(int i=;i<=n;i++){
node x;
x.ans=a[i]+b[];
x.bb=;
q.push(x);
}
for(int i=;i<=n;i++){
node now=q.top();
q.pop();
cout<<now.ans<<" ";
now.bb++;
now.ans=now.ans+b[now.bb]-b[now.bb-];
q.push(now);
}
return ;
}