• 洛谷1631 序列合并（优先队列）

    题目描述

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

    输入格式

    第一行一个正整数 N；

    第二行 N 个整数 1…A1…N​。

    第三行 N 个整数 1…B1…N​。

    输出格式

    一行 N 个整数，从小到大表示这 N 个最小的和。

    输入输出样例

    输入 #1复制

    3
2 6 6
1 4 8

    输出 #1复制

    3 6 7

    说明/提示

    对于 50%50% 的数据，N≤103。

    对于 100%100% 的数据，1≤N≤105，1≤ai​,bi​≤109。

    思路： 

    看的题解，n^2个和，可以分成n个序列。

    A[1]+B[1] <= A[1]+B[2] <= … <= A[1]+B[N]

    A[2]+B[1] <= A[2]+B[2] <= … <= A[2]+B[N]

    ……

    A[N]+B[1] <= A[N]+B[2] <= … <= A[N]+B[N]

    对于每一个序列，我们维护一个最小值，用优先对列，当某一行一个数被输出，我们就让这行下一值进入优先队列。

    代码：

    #define _CRT_SECURE_NO_WARNINGS
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    #define LL long long
    #define per(i,a,b) for(int i=a;i<=b;i++)
    #define rep(i,a,b) for(int i=a;i>=b;i--)
    const int N = 1e5 + 100;
    LL n, a[N], b[N];
    struct data
    {
        int no;
        int j;
        LL cn;
    }d;
    bool operator > (const struct data& a, const struct data& b)
    {
        return a.cn > b.cn;
    }
    priority_queue, greater >p;
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0), cout.tie(0);
        cin >> n;
        per(i, 1, n)
            cin >> a[i];
        per(i, 1, n)
            cin >> b[i];
        per(i, 1, n)
        {
            d = { i,1,a[i] + b[1]};
            p.push(d);
        }
        int cnt = 0;
        while (!p.empty())
        {
            d = p.top();
            p.pop();
            cout << d.cn << " ", cnt++;
            if (cnt == n)
                break;
            if(d.j+1<=n)
            p.push({ d.no,d.j+1,a[d.no] + b[d.j + 1]});
        }
        return 0;
    }

  • 相关阅读:
    代码随想录Day59 | 647. 回文子串 | 516. 最长回文子序列
    libcurl库
    Video.js实现在html页面播放rtmp流媒体
    【图像分类】2022-CMT CVPR
    ssm+vue的4S店预约保养管理系统（有报告）。Javaee项目，ssm vue前后端分离项目。
    React之受控组件和非受控组件以及高阶组件
    稳压二极管的原理，它有什么作用？
    Options Error: invalid boolean value
    PostgreSQL13 安装
    计算机毕业论文选题java毕业设计软件基于SSM实现的固定资产管理系统
  • 原文地址：https://blog.csdn.net/yusen_123/article/details/133717415