欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

N个最小和

程序员文章站 2022-06-04 17:29:24
...

N个最小和

N个最小和

思路:每次添加一个值到优先队列中。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <set>
#include <sstream>
#include<string>
#include<queue>
#include<stack>
#include<map>
#define MAXX 100005
#define SIS std::ios::sync_with_stdio(false)
#define ll long long
#define INF 0x3f3f3f3f
//#include<bits/stdc++.h>
using namespace std;
//const int MAX =100;
const double PI = 3.14159265359;
//const int esp = 1e9 + 7;
int n, m;
struct node
{
    int x, y, num;
    bool operator <(const node other)const
    {
        return num > other.num;
        
    }
};
int a[100000], b[100000];
priority_queue<node> pq;
int main()
{
   
    SIS;
    cin >> n;
    node tm;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    sort(a, a + n);
    sort(b, b + n);
    for (int i = 0; i < n; i++)
    {
        tm.x = 0;
        tm.y = i;
        tm.num = a[0] + b[i];
        pq.push(tm);
    }
    for (int i = 0; i < n; i++)
    {
        tm = pq.top();
        pq.pop();
        if (i != n - 1)
        {
            cout << tm.num << ' ';
        }
        else
            cout << tm.num << endl;
        if (tm.x != n - 1)
        {
            tm.num = a[++tm.x] + b[tm.y];
            pq.push(tm);
        }

    }

    return 0;

}

相关标签: 技巧