题目

传送门= ̄ω ̄=

题目描述

有两个长度都是N的序列A和B,在A和B中各取一个数相加可以得到N^2个和,求这N^2个和中最小的N个。

输入输出格式

输入格式:

第一行一个正整数N;

第二行N个整数Ai,满足Ai<=Ai+1且Ai<=10^9;

第三行N个整数Bi, 满足Bi<=Bi+1且Bi<=10^9.

【数据规模】

对于50%的数据中,满足1<=N<=1000;

对于100%的数据中,满足1<=N<=100000。

输出格式:

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

输入输出样例

输入样例#1:

3
2 6 6
1 4 8

输出样例#1:

3 6 7

题解

首先a、b从小到大排序。
众所周知,最小的数字就是$a[1]+b[1]$
那么第二个数字一定是$a[1]+b[2]$、$a[2]+b[1]$中的一个!
所以设当前最小的是$a[l]+b[r]$
那么下一个答案就存在于$a[l]+b[r+1]$和$a[l+1]+b[r]$中。
所以我们搞个优先队列,每次取出最小的输出,并对它进行扩展。
复杂度$O(nlogn)$

优先队列STL自带。

代码:

#include <bits/stdc++.h>
using namespace std;
template<typename tp>void in(tp & dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
int n,a[100005],b[100005],ans[100005];
set<int> book[100005];
struct node
{
    int l,r;
    bool operator < (node oth)const{return a[oth.l]+b[oth.r]<a[l]+b[r];}
};
priority_queue<node> pq;
int main()
{
    in(n);
    for(int i=1;i<=n;in(a[i++]));
    for(int i=1;i<=n;in(b[i++]));
    sort(b+1,b+1+n),sort(a+1,a+1+n),pq.push((node){1,1});
    for(int i=1;i<=n;i++)
    {
        node f=pq.top();pq.pop();
        printf("%d ",a[f.l]+b[f.r]);
        if(f.l<n&&!book[f.l+1].count(f.r))
            pq.push((node){f.l+1,f.r}),book[f.l+1].insert(f.r);
        if(f.r<n&&!book[f.l].count(f.r+1))
            pq.push((node){f.l,f.r+1}),book[f.l].insert(f.r+1);
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *