江苏住房和城乡建设厅网站,wordpress做资源下载站,义乌高端网站建设,阿里巴巴网站备案号题目描述 问题#xff1a;序列和的前n小元素 给出两个长度为n的有序表A和B, 在A和B中各任取一个, 可以得到 n^2 个和. 求这些和最小的n个。
输入输出格式
输入格式#xff1a; 输入数据共三行。 第一行#xff0c;一个整数值n #xff08; n 10^4 #xff…题目描述 问题序列和的前n小元素 给出两个长度为n的有序表A和B, 在A和B中各任取一个, 可以得到 n^2 个和. 求这些和最小的n个。
输入输出格式
输入格式 输入数据共三行。 第一行一个整数值n n 10^4 。 第二第三行各有n个从小到大排好序的整数每个整数间有一个空格间隔。每个整数均小于2^30
输出格式 输出数据一行,这些和最小的n个数从小到大输出每个整数之间一个空格间隔。
输入输出样例
输入样例#1
10 158443636 284841496 317570810 452077938 476117840 485745865 646752262 998776724 1022863800 1038269864 8345019 96770572 114185139 211677750 365253930 495542735 670357622 765440815 783523273 835082336
输出样例#1
166788655 255214208 272628775 293186515 325915829 370121386 381612068 399026635 414341382 431755949
提示信息
数据范围 30%数据n 10^2。 50%数据n 10^3。 100%数据n 10^4。 算法分析
二叉堆模板题用优先队列实现
思路
暴力枚举每个数使堆内始终有n个数。
题中有“两个长度为n的有序表A和B”
故在第二层循环时若已有n个数则只需判断一次即可退出循环。
#includebits/stdc.h
using namespace std;
priority_queueint,vectorint p;
int a[1000010];
int b[1000010];
int c[1000010];
int n,len;
int main()
{cinn;for(int i1;in;i)cina[i];for(int i1;in;i)cinb[i];for(int i1;in;i){for(int j1;jn;j){if(lenn){p.push(a[i]b[j]);len;}//先把堆填充满n个数else{if(a[i]b[j]p.top()){p.pop();p.push(a[i]b[j]);}//优先要小的比堆头小就扔掉堆头else break;//如果a[i]b[j]小于堆头,那么对于有序表b来说a[i]b[j1]必定大于堆头}}}len0;while(!p.empty()){c[len]p.top();p.pop();}for(int i1;in;i){coutc[n-i1] ;}return 0;
}
