西昌网站建设公司,长沙景点,青岛免费网站建站模板,镇江大港题目描述 有两个长度都是N的序列A和B#xff0c;在A和B中各取一个数相加可以得到N^2N2个和#xff0c;求这N^2N2个和中最小的N个。 输入输出格式 输入格式#xff1a; 第一行一个正整数N#xff1b; 第二行N个整数A_iAi, 满足A_i\le A_{i1}Ai≤Ai1且A_i\le 10^9Ai≤…题目描述 有两个长度都是N的序列A和B在A和B中各取一个数相加可以得到N^2N2个和求这N^2N2个和中最小的N个。 输入输出格式 输入格式 第一行一个正整数N 第二行N个整数A_iAi, 满足A_i\le A_{i1}Ai≤Ai1且A_i\le 10^9Ai≤109; 第三行N个整数B_iBi, 满足B_i\le B_{i1}Bi≤Bi1且B_i\le 10^9Bi≤109. 【数据规模】 对于50%的数据中满足1N1000 对于100%的数据中满足1N100000。 输出格式 输出仅一行包含N个整数从小到大输出这N个最小的和相邻数字之间用空格隔开。 输入输出样例 输入样例#1 3
2 6 6
1 4 8 输出样例#1 3 6 7 题解 其实就是每次找最小的两个但是题目是每个数可以用多次如何不重复的去做才是终点首先对于A序列的第一个数一定是要选的那么就可以先把B数列中所有数与它的和加入优先队列中并记录下当前与A序列第一个数相加可以用P数组存那么每次就输出队首这个没问题吧然后将对首的A数列变后一个将之前记录P数组1再加上自己再加入队列里代码 1 #include cstdio2 #include queue3 #include vector4 #define N 1000105 using namespace std;6 priority_queuepairint,int,vectorpairint,int ,greaterpairint,int Q;7 int n,k,a[N],b[N],p[N];8 int main()9 {
10 scanf(%d,n);
11 for (int i1;in;i) scanf(%d,a[i]);
12 for (int i1;in;i) scanf(%d,b[i]),p[i]1,Q.push(make_pair(a[1]b[i],i));
13 while (n--) printf(%d ,Q.top().first),kQ.top().second,Q.pop(),Q.push(make_pair(a[p[k]]b[k],k));
14 } 转载于:https://www.cnblogs.com/Comfortable/p/10327991.html
