描述
有两个长度为 N 的序列 A 和 B, 在 A 和 B 中各任取一个数相加可以得到 N^2 个和, 求这 N^2 个和中最小的 N 个.
输入
第一行输入一个正整数 N(N<=10^5); 第二行 N 个整数 Ai 且 Ai<=10^9; 第三行 N 个整数 Bi 且 Bi<=10^9.
输出
输出仅一行, 包含 n 个整数, 从小到大输出这 n 个最小的和, 相邻数字之间用空格隔开.
输入样例 1
- 5
- 1 3 2 4 5
- 6 3 4 1 7
输出样例 1
2 3 4 4 5
输入样例 2
- 10
- -1 3 2 0 12 6 2 3 -5 5
- -3 2 5 1 0 12 32 -2 2 3
输出样例 2
- -8 -7 -5 -4 -4 -3 -3 -3 -3 -2
- #include <bits/stdc++.h>
- using namespace std;
- long long a[100005];
- long long b[100005];
- struct note{
- int num,y;
- bool operator <(const note&a)const{
- return num>a.num;
- }
- };
- priority_queue <note> q;
- int main()
- {
- int n;
- cin>>n;
- int d;
- note k;
- for(int i=1;i<=n;i++)
- cin>>a[i];
- for(int i=1;i<=n;i++)
- cin>>b[i];
- sort(a+1,a+n+1,Less<int>());
- sort(b+1,b+n+1,Less<int>());
- for(int i=1;i<=n;i++)
- {
- k.y=1;
- k.num=a[i]+b[1];
- q.push(k);
- }
- int flag=0;
- for(int i=1;i<=n;i++)
- {
- k=q.top();
- q.pop();
- d=k.num;
- int y=k.y;
- k.num=d-b[y]+b[y+1];
- k.y=y+1;
- q.push(k);
- if(flag==0)
- {
- cout<<d;
- flag=1;
- }
- else
- cout<<" "<<d;
- }
- cout<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3001100.html