题解 P1631 【序列合并】
梦回还
2017-11-24 12:39:17
本人的思路同楼下众大佬一致，就是做法不太一样，可以参考参考。
我们发现对于两个序列中的数，a[i]+b[j]<a[i+1]+b[j]，a[i]+b[j]<a[i]+b[j+1]；
并且很明显有a[1]+b[1]<a[2]+b[2]<……那么我们将其和（N个）压入优先队列。
只要有 i==j 的点被弹出，我们就把 a[i+1]+b[i] 与a[i]+b[i+1] 压入优先队列,
否则，当 i<j 时，将 a[i]+b[j+1] 压入即可； 当 i>j 时，将 a[i+1]+b[j] 压入。
为什么 i<j 时不压入 a[i+1]+b[j] ？我们考虑到此时 a[i+1]+ b[j-1] 及之前的数字可能依旧在优先队列中并且更优，就不必更新。
i>j 时不压入 a[i]+b[j+1],同理。
```cpp
#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100005;
struct data{
int x, y, v;
bool operator <(const data &y) const{
return v > y.v;
}
};
int n, a[N], b[N], X[N], Y[N];
priority_queue<data> pq;
//在结构体中重定义小于号，维护一个小根堆
int read()
{
int x = 0;
bool f = 0;
char ch = getchar();
while(!isdigit(ch)) {
if(ch == '-') f = 1;
ch = getchar();
}
while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch =getchar();
return !f ? x : -x;
}
//优雅的读入优化
int main()
{
scanf("%d",&n);
data x, y, k;
int tot = n;
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= n; i++) scanf("%d",&b[i]);
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
for(int i = 1; i <= n; i++) k.x = k.y = i, k.v = a[i] + b[i], pq.push(k);
for(int i = 1; i <= n; i++)
{
k = pq.top(); pq.pop();
printf("%d ", k.v);
if(k.x == k.y)
{
x.x = k.x; x.y = k.y + 1; x.v = a[x.x] + b[x.y]; pq.push(x);
y.x = k.x + 1; y.y = k.y; y.v = a[y.x] + b[y.y]; pq.push(y);
}
else
{
if(k.x > k.y) y.x = k.x + 1, y.y = k.y, y.v = a[y.x] + b[y.y], pq.push(y);
else x.x = k.x, x.y = k.y + 1, x.v = a[x.x] + b[x.y], pq.push(x);
}
}
return 0;
}
```