ZZULI 2269: minval【优先队列】

亦凉 2022-05-26 03:05 20阅读 0赞

## 2269: minval ##

时间限制: 3 Sec 内存限制: 256 MB  
提交: 765 解决: 112  
\[提交\]\[状态\]\[讨论版\]\[命题人:外部导入\]

#### 题目描述 ####

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

#### 输入 ####

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

第二行N个整数Ai且Ai<=109；第三行N个整数Bi且Bi<=109。

#### 输出 ####

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

#### 样例输入 ####

5  
1 3 2 4 5  
6 3 4 1 7

#### 样例输出 ####

2 3 4 4 5

#### 解题分析： ####

数据虽然非常大，但是只用算出前n个就可以了。所以先对两组数据用sort从小到大排个序，然后用第一个数加就可以了，但因为可能出现第二组数据的第一个数比第一组数据的第一个数大，但第二个数比第一组数据的第二，甚至第三第四都小的情况，所以要用优先队列。

#### AC代码： ####

#include<stdio.h>
    #include<string.h>
    #include<queue>
    #include<algorithm>
    using namespace std;
    
    #define N 100005
    
    struct edge{
        int v, x;
    };
    
    int a[N], b[N];
    
    bool operator < (const edge &c, const edge &d)
    {
        return c.v > d.v;
    }
    
    int main()
    {
        struct edge tmp;
        int i, j, n;
        priority_queue<edge> q;
        while(~scanf("%d", &n)){
            for(i = 0; i < n; i++) scanf("%d", &a[i]);
            for(i = 0; i < n; i++) scanf("%d", &b[i]);
            sort(a, a+n);
            sort(b, b+n);
            for(i = 0; i < n; i++){
                tmp.v = a[0]+b[i];
                tmp.x = 0;
                q.push(tmp);
            }
            while(n--){
                tmp = q.top();
                q.pop();
                printf("%d ", tmp.v);
                tmp.v += a[tmp.x+1]-a[tmp.x];
                tmp.x++;
                q.push(tmp);
            }
            printf("\n");
        }
        return 0;
    }