设行为
A
i
A_i
Ai 列为
B
j
B_j
Bj
由题知,很显然排完序的A数组与B数组的和呈此关系,那也知道
A
1
+
B
1
A_1+B_1
A1+B1的值是最小的,其余关系如图。
证明:
a i < a i + 1 , a_i<a_{i+1}, ai<ai+1,在 b j b_j bj一定时, a i + b j < a i + 1 + b j a_i+b_j<a_{i+1}+b_j ai+bj<ai+1+bj
b i < b i + 1 , b_i<b_{i+1}, bi<bi+1,在 a j a_j aj一定时, b i + a j < b i + 1 + a j b_i+a_j<b_{i+1}+a_j bi+aj<bi+1+aj
所以左上角最小,右下角最大
那我们可以先把
a
i
+
b
1
a_i+b_1
ai+b1加入到优先队列中,然后弹出最小的,假设这个最小值是由
a
x
+
b
y
a_x+b_y
ax+by构成,那么再把
a
x
+
b
y
+
1
a_x+b_{y+1}
ax+by+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;
}