https://www.luogu.org/problem/show?pid=1631
题目描述
有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2个和，求这N^2个和中最小的N个。
输入输出格式
输入格式：
第一行一个正整数N；
第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;
第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9.
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
输出格式：
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入输出样例
输入样例#1：
3 2 6 6 1 4 8
输出样例#1：
优先队列T2ge
3 6 7
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdio> 4 #define N 100015 5 6 using namespace std; 7 8 int n,size,a[N],b[N]; 9 int heap[N],ans[N]; 10 11 void push(int x) 12 { 13 heap[++size]=x; 14 int now=size,next; 15 while(now>1) 16 { 17 next=now/2; 18 if(heap[next]>=heap[now]) break; 19 swap(heap[next],heap[now]); 20 now=next; 21 } 22 23 } 24 25 void pop() 26 { 27 heap[1]=heap[size--]; 28 int now=1,next; 29 while(now*2<=size) 30 { 31 next=now*2; 32 if(next<size&&heap[next]<heap[next+1]) next++; 33 if(heap[now]>=heap[next]) break; 34 swap(heap[now],heap[next]); 35 now=next; 36 } 37 } 38 39 int main() 40 { 41 scanf("%d",&n); 42 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 43 for(int i=1;i<=n;i++) scanf("%d",&b[i]); 44 sort(a+1,a+n+1); 45 sort(b+1,b+n+1); 46 for(int i=1;i<=n;i++) push(a[1]+b[i]); 47 for(int i=2;i<=n;i++) 48 for(int j=1;j<=n;j++) 49 { 50 if(heap[1]>a[i]+b[j]) 51 { 52 pop(); 53 push(a[i]+b[j]); 54 } 55 else break; 56 } 57 for(int i=1;i<=n;i++) 58 { 59 ans[i]=heap[1]; 60 pop(); 61 } 62 while(n--) 63 { 64 printf("%d ",ans[n+1]); 65 } 66 return 0; 67 }