洛谷刷题之p1631

序列合并

题目入口

题目描述

有两个长度为 $N$ 的单调不降序列 $A,B$，在 $A,B$ 中各取一个数相加可以得到 $N^2$ 个和，求这 $N^2$ 个和中最小的 $N$ 个。

输入格式

第一行一个正整数 $N$；

第二行 $N$ 个整数 $A_{1\dots N}$。

第三行 $N$ 个整数 $B_{1\dots N}$。

输出格式

一行 $N$ 个整数，从小到大表示这 $N$ 个最小的和。

样例 #1

样例输入 #1

3
2 6 6
1 4 8

样例输出 #1

3 6 7

提示

对于 $50\%$ 的数据，$N\le 10^3$。

对于 $100\%$ 的数据，$1\le N\le 10^5$，$1\le a_i,b_i\le 10^9$。

题解

设行为$A_i$ 列为$B_j$
由题知，很显然排完序的A数组与B数组的和呈此关系，那也知道$A_1+B_1$的值是最小的，其余关系如图。

证明：
$a_i<a_{i+1},$在$b_j$一定时，$a_i+b_j<a_{i+1}+b_j$
$b_i<b_{i+1},$在$a_j$一定时，$b_i+a_j<b_{i+1}+a_j$
所以左上角最小，右下角最大

那我们可以先把$a_i+b_1$加入到优先队列中，然后弹出最小的，假设这个最小值是由$a_x+b_y$构成，那么再把$a_x+b_{y+1}$放入优先队列中
最后记得重载运算符

Code

#include <bits/stdc++.h>using namespace std;const int Maxn = 1e5 + 10;
int pos_b[Maxn];
int a[Maxn], b[Maxn];
int id[Maxn];
struct node
{int pos;int num;bool operator<(const node &cur) const{return num > cur.num;}
};
priority_queue<node> c;
int n;
void read()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){cin >> b[i];}
}
void solve()
{sort(a + 1, a + n + 1);sort(b + 1, b + n + 1);for (int i = 1; i <= n; i++){c.push({i, a[i] + b[1]});id[i] = 1;}for (int i = 1; i <= n; i++){node x = c.top();c.pop();cout << x.num << " ";int id2 = x.pos;c.push({id2, a[id2] + b[++id[id2]]});}
}
int main()
{read();solve();return 0;
}