品牌网站建设哪好,网站如何做诺顿认证,织梦网站模板免费下载,贵州seo排名题目描述
有两个长度为 N 的单调不降序列 ,A,B#xff0c;在 A,B 中各取一个数相加可以得到 N2 个和#xff0c;求这 N2 个和中最小的 N 个。
输入格式
第一行一个正整数 N#xff1b;
第二行 N 个整数 1…A1…N。
第三行 N 个整数 1…B1…N。
输出格式
一行 N 个…题目描述
有两个长度为 N 的单调不降序列 ,A,B在 A,B 中各取一个数相加可以得到 N2 个和求这 N2 个和中最小的 N 个。
输入格式
第一行一个正整数 N
第二行 N 个整数 1…A1…N。
第三行 N 个整数 1…B1…N。
输出格式
一行 N 个整数从小到大表示这 N 个最小的和。
输入输出样例
输入 #1复制
3
2 6 6
1 4 8
输出 #1复制
3 6 7
说明/提示
对于 50%50% 的数据N≤103。
对于 100%100% 的数据1≤N≤1051≤ai,bi≤109。
思路
看的题解n^2个和可以分成n个序列。
A[1]B[1] A[1]B[2] … A[1]B[N]
A[2]B[1] A[2]B[2] … A[2]B[N]
……
A[N]B[1] A[N]B[2] … A[N]B[N]
对于每一个序列我们维护一个最小值用优先对列当某一行一个数被输出我们就让这行下一值进入优先队列。
代码
#define _CRT_SECURE_NO_WARNINGS #includeiostream #includecstdio #includecstdlib #includestring #includecstring #includecmath #includectime #includealgorithm #includeutility #includestack #includequeue #includevector #includeset #includemath.h #includeunordered_map #includemap using namespace std; #define LL long long #define per(i,a,b) for(int ia;ib;i) #define rep(i,a,b) for(int ia;ib;i--) const int N 1e5 100; LL n, a[N], b[N]; struct data { int no; int j; LL cn; }d; bool operator (const struct data a, const struct data b) { return a.cn b.cn; } priority_queuestruct data, vectorstruct data, greaterstruct data p; int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin n; per(i, 1, n) cin a[i]; per(i, 1, n) cin b[i]; per(i, 1, n) { d { i,1,a[i] b[1]}; p.push(d); } int cnt 0; while (!p.empty()) { d p.top(); p.pop(); cout d.cn , cnt; if (cnt n) break; if(d.j1n) p.push({ d.no,d.j1,a[d.no] b[d.j 1]}); } return 0; }
