zzuliOJ 2269 minval(优先队列)

Description:

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

Input:

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

第二行N个整数Ai且 $Ai\&lt;=10^9$Ai<=109；第三行N个整数Bi且 $Bi\&lt;=10^9$Bi<=109 。

Output:

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

Sample Input:

5
1 3 2 4 5
6 3 4 1 7

Sample Output:

2 3 4 4 5

题目连接

这道题目直接暴力求出n*n个结果然后排序不用想肯定是超时的，所以就需要在这个基础上进行一些优化，把a,b两个数列先按照升序排序，然后用一个降序优先队列存储相加结果，不断维护这个优先队列。先把a数列第一个数和b数列所有数之和添加进优先队列，之后从a数列第二个数开始继续枚举和b数列各个数之和，若和大于优先队列队首则跳出循环，进行a数列下一个数的枚举，否则就将和添加进队列，并将队首元素pop出来，若枚举到的a数列元素与b数列第一个元素之和大于优先队列队首元素则直接跳出所有枚举。最后按照题目要求输出结果。
当时在比赛的时候因为这题目“运行错误”卡了很长时间也没有做出来，之后发现是因为使用cin&&cout进行数据输入输出时用

ios::sync_with_stdio(0);
cin.tie(0);

关闭了同步流导致，把这两行代码注释掉或者将cin&&cout换为scanf&&printf就可以AC。找到原因的我感觉一脸蒙逼，完全不知道为什么会出现这样的“玄学”错误。

AC代码:

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <cctype>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>
#include <sstream>
#include <set>
#include <map>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
typedef long long ll;
typedef pair<int,int> P;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;
const double eps = 1e-5;
const double pi = asin(1.0)*2;
const double e = 2.718281828459;

int n;
int a[maxn], b[maxn];
priority_queue<int> que;

void Output_res() {
    if (que.empty()) {
        return;
    }
    else {
        int output_temp = que.top();
        que.pop();
        Output_res();
        printf("%d ", output_temp);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &b[i]);
        que.push(a[1] + b[i]);
    }
    sort(b + 1, b + n + 1);
    for (int i = 2; i <= n; ++i) {
        if (a[i] + b[1] > que.top()) {
            break;
        }
        for (int j = 1; j <= n; ++j) {
            if (a[i] + b[j] > que.top()) {
                break;
            }
            que.push(a[i] + b[j]);
            que.pop();
        }
    }
    Output_res();
    return 0;
}