有两个长度都是N的序列A和B，在A和B中各取一个数相加可以得到N^2N2个和，求这N^2N2个和中最小的N个。
第一行一个正整数N；
第二行N个整数A_iAi?, 满足A_i\le A_{i+1}Ai?≤Ai+1?且A_i\le 10^9Ai?≤109;
第三行N个整数B_iBi?, 满足B_i\le B_{i+1}Bi?≤Bi+1?且B_i\le 10^9Bi?≤109.
【数据规模】
对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。
输出仅一行，包含N个整数，从小到大输出这N个最小的和，相邻数字之间用空格隔开。
输入 #1
3 2 6 6 1 4 8
输出 #1
3 6 7
最开始的想法，wa了，还是太年轻了。。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <algorithm> 6 const int INF=0x3f3f3f3f; 7 using namespace std; 8 int A[100010]; 9 int B[100010]; 10 11 12 int main() 13 { 14 int n; 15 scanf("%d",&n); 16 memset(A,INF,sizeof(A)); 17 memset(B,INF,sizeof(B)); 18 for(int i=0;i<n;i++) 19 { 20 scanf("%d",&A[i]); 21 } 22 for(int i=0;i<n;i++) 23 { 24 scanf("%d",&B[i]); 25 } 26 printf("%lld",A[0]+B[0]); 27 int cnt=1; 28 int p=1,q=1; 29 while(cnt<n) 30 { 31 if(A[0]+B[p]<=B[0]+A[q]) 32 { 33 printf(" %lld",A[0]+B[p]); 34 p++; 35 cnt++; 36 } 37 else if(A[0]+B[p]>B[0]+A[q]) 38 { 39 printf(" %lld",B[0]+A[q]); 40 q++; 41 cnt++; 42 } 43 } 44 printf("\n"); 45 return 0; 46 }
看了题解，什么用堆做，用优先队列做。。。。
看懂了优先队列的那种
因为两个序列都是不下降的有序序列，所以满足以下不等式
a1+b1<=a2+b1<=a3+b1<=...<=an+b1 t[1]=1;
a1+b2<=a2+b2<=a3+b2<=...<=an+b2 t[2]=1;
a1+b3<=a2+b3<=a3+b3<=...<=an+b3 t[3]=1;
...
a1+bn<=a2+bn<=a3+bn<=...<=an+bn t[n]=1;
所以，这n^n个和里的最小值在a1+b1,a1+b2...a1+bn里（这时最小的当然是a1+b1），然后去掉最小的a1+b1,剩下的不等式变为以下
a2+b1<=a3+b1<=a4+b1<=...<=an+b1 t[1]=2;
a1+b2<=a2+b2<=a3+b2<=...<=an+b2 t[2]=1;
a1+b3<=a2+b3<=a3+b3<=...<=an+b3 t[3]=1;
...
a1+bn<=a2+bn<=a3+bn<=...<=an+bn t[n]=1;
最小值还是第一列的那n个和里最小的。所以始终用优先队列维护n个和，直到得到最小的N个和。
这里用t数组存上方每一行中到了第几个式子了，也就是a的下标；
优先队列中存的是pair
first就是上方的第一列的式子结果，second存的是该行式子b的下标，可以根据这个找到相应的t值
下面给出代码：
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <string> 5 #include <algorithm> 6 #include <queue> 7 const int INF=0x3f3f3f3f; 8 using namespace std; 9 int a[100010],b[100010],t[100010]; 10 priority_queue<pair<int,int>,vector<pair<int ,int> >,greater<pair<int,int> > > qe; 11 12 int main() 13 { 14 int n; 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++) 17 { 18 scanf("%d",&a[i]); 19 } 20 for(int i=1;i<=n;i++) 21 { 22 scanf("%d",&b[i]); 23 qe.push(make_pair(a[1]+b[i],i)); 24 t[i]=1; 25 } 26 for(int i=1;i<=n;i++) 27 { 28 printf("%d ",qe.top().first); 29 int m=qe.top().second; 30 t[m]++; 31 qe.pop(); 32 qe.push(make_pair(a[t[m]]+b[m],m)); 33 } 34 return 0; 35 }
原文：https://www.cnblogs.com/jiamian/p/11255455.html
