一、题目描述

原题链接

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

二、解题思路

  本题最后需要求的是和的前 $N$ 小的数，换言之就是将其他大的数都排除掉，因此直接用大根堆来存也比较好做。首先想暴力解，很显然遍历数组 $A$ 从 $1-n$，数组 $B$ 也是从 $1 - n$，将 $A[i] + B[j]$ 存入到堆中，将大数不断弹出，最后保留下来的 $N$ 个数就是最终的解，时间复杂度 $O(N^2 logN)$，很显然是无法通过此题的。

  如何优化？我们发现在堆的长度已经饱和的情况下，若 $B[j]$ 无法入队，也就意味着 $ B[j+1] $ 也无法入队，这时就可以提前 break 掉，经过优化后的方法时间复杂度来到 $ O(Nlog^2N) $，可以通过此题。

三、AC代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

priority_queue<ll> q;

const int N = 100010;
int a[N];
int b[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]);
    }
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            if(q.size()<n){
                q.push(a[i] + b[j]);
            }else{
                if(a[i] + b[j] < q.top()){
                    q.pop();
                    q.push(a[i] + b[j]);
                }else break;
            }
        }
    }
    vector<ll> ans;
    for(int i = 1;i<=n;i++){
        ans.push_back(q.top());
        q.pop();
    }
    for(int i = ans.size()-1;i>=0;i--){
        printf("%lld ",ans[i]);
    }
    cout << endl;
    system("pause");
    return 0;
}