题目大意

　　有两个序列A，B，在A和B中各取一个数相加能得到$n^2$个和。求出这些和前n小的数字。

题解

　　首先这道题不可以用自己想的什么A序列B序列各两个指针的自己发明的模拟算法，用这样的算法只能是绝路一条。

　　此题入手点在于优化暴力。暴力算法是枚举所有的$A_i+B_j$，排个序，然后一个个输出。我们优化之处便是如何动态枚举$A_i,B_j$。

　　此时我曾想对两个数组都动态，这样想就走到了死胡同。

　　我们可以让A不动态，B动态，也就是优先队列里储存的数对里包含所有的$A_i$，但每个$A_I$只对应一个$B_j$。每次出队时，将$A_i$对应的$B_j$的j++再推入队列中。这样便有解了。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int MAX_N = 100010, INF = 0x3f3f3f3f;

int A[MAX_N], B[MAX_N];

struct Element

{

    int AId, BId;

    Element(int aId, int bId):AId(aId), BId(bId){}

    bool operator < (const Element a) const

    {

        return A[AId] + B[BId] > A[a.AId] + B[a.BId];

    }

};

priority_queue<Element> q;

int main()

{

    int n;

    scanf("%d", &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(Element(i, 1));

    for (int i = 1; i <= n; i++)

    {

        Element cur = q.top();

        q.pop();

        printf("%d ", A[cur.AId] + B[cur.BId]);

        if (cur.BId < n)

        {

            cur.BId++;

            q.push(cur);

        }

    }

    return 0;

}

巴特西

luogu1631 序列合并

题目大意

题解

最新文章

热门文章