題目描述

　　問題：序列和的前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個數，則只需判斷一次即可退出循環。

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int> > p;
int a[1000010];
int b[1000010];
int c[1000010];
int n,len;
int main()
{cin>>n;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(len<n){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[j+1]必定大于堆頭}}}len=0;while(!p.empty()){c[++len]=p.top();p.pop();}for(int i=1;i<=n;i++){cout<<c[n-i+1]<<' ';}return 0;
}