minval （优先队列 priority_queue）_综合

题目描述

有两个长度为N的序列A和B，在A和B中各任取一个数相加可以得到N2个和，求这N2个和中最小的N个。

输入

第一行输入一个正整数N（1<=N<=100000）；

第二行N个整数Ai且Ai<=109；第三行N个整数Bi且Bi<=109。

输出

输出仅一行，包含n个整数，从小到大输出这n个最小的和，相邻数字之间用空格隔开。

样例输入

1 3 2 4 5

6 3 4 1 7

样例输出

2 3 4 4 5

思路：

这道题要用到优先队列：

priority_queue <int> q;

// 升序优先队列，队首数值最大

把两个数组进行排序（升序），然后用 a[1] 加上 b[1...n] 一共 n 个数入队。

然后暴力枚举，如果a[i]+a[j]（i【2->n】， j【1->n】）如果小于队首，队首出队，a[i]+a[j] 入队。

最差的时间复杂度会不会出现 n^2 的时间复杂度：

不会，时间复杂度应该为，n+n/2 + n/4 ... +n/(2^n-1) 近似等于 2*n。

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>using namespace std;priority_queue <int> q;// 升序优先队列，队首数值最大 const int N = 100100;
int a[N], b[N], res[N];int main(){int n;cin >> n;for(int i=1; i<=n; i++) {scanf("%d", &a[i]);}for(int i=1; i<=n; i++) {scanf("%d", &b[i]);}sort(a+1, a+n+1);sort(b+1, b+n+1);for(int i=1; i<=n; i++) {q.push( a[1]+b[i] );}for(int i=2; i<=n; i++) {for(int j=1; j<=n; j++) {if(a[i]+b[j] < q.top()) {//  cout << a[i]+b[j] << endl;q.pop();q.push(a[i]+b[j]);}elsebreak;}}int t = 0;for(int i=1; i<=n; i++) {res[++t] = q.top();q.pop();}for(int i=n; i>=1; i--) {printf("%d ",res[i]);}return 0;
}