北京seo关键词_好的ppt模板免费下载网站_seo入门课程_网站seo顾问

问题描述

有两个长度为 $n$ 的序列 $a$ 和 $b$ ，在 $a$ 和 $b$ 中各任取一个数相加可以得到 $n^2$ 个和，求这 $n^2$ 个和中最小的 $n$ 个。

输入格式

第一行输入一个正整数 $n$ 。
第二行 $n$ 个整数 $a_i$。
第三行 $n$ 个整数 $b_i$。

输出格式

第一行 $n$ 个整数，从小到大输出这 $n$ 个最小的和，相邻数字之间用空格隔开。

样例

样例输入1：

5
1 3 2 4 5
6 3 4 1 7

样例输出1：

2 3 4 4 5

数据范围

对于 $50\%$ 的数据，$1\le n\le 1000$。
对于 $100\%$ 的数据，$1\le n\le 100000$，$1\le a_i,b_i\le 10^9$。

题解

先将 $a$ 和 $b$ 从小到大排序，显然，$a_1\le a_2\le \dots \le a_n$，$b_1\le b_2\le \dots \le b_n$。

先将 $a_1+b_1$，$a_1+b_2$，$\dots$，$a_1+b_n$ 放进堆里，并把 $a_1$ 的编号 $1$ 记录下来。

最先取出 $a_1+b_1$，输出，并继续放入 $a_2+b_1$，第二小的在 $a_2+b_1$ 和 $a_1+b_i(2\le i\le n)$ 之间。

可以证明其正确性：

$a_1+b_i\le a_2+b_i\le a_3+b_i\le \dots a_n+b_i$

那么如果取出了 $a_x+b_y$，则放出大于它的且最接近的 $a_{x+1}+b_y$，能保证递增性质。

//定义大根堆 q
priority_queue<pi, vector<pi>, greater<pi>> q;
输入 n, 数组a, 数组b
a, b 从小到大排序
//初始放入
for(int i = 1; i <= n; ++ i){q.push({a[1] + b[i], 1});
}
for(int i = 1; i <= n; ++ i){pi pr = q.top();//输出printf("%d\n", pr.first);q.push({pr.first - a[pr.second] + a[pr.second + 1], pr.second + 1});
}