问题 M: 序列合并

问题 M: 序列合并

http://exam.upc.edu.cn/problem.php?cid=1444&pid=12

时间限制: 1 Sec  内存限制: 64 MB
提交: 748  解决: 176
[提交] [状态] [讨论版] [命题人:admin]

题目描述

有两个长度都是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.

 

输出

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

 

样例输入

3
2 6 6
1 4 8

 

样例输出

3 6 7 

 

提示

 

对于50%的数据中，满足1<=N<=1000；
对于100%的数据中，满足1<=N<=100000。

 

思路：先让b都+a[0]，找最小，让最小和的加数b往后+a。排序，重复此过程n次。

      嗯。。用数组做超时，就用的优先队列。。。不造为什么数组会超时，难道优先队列排序不耗时吗？？？求大神解答！！

以样例解释：（辛苦花了半天，果然电脑画图还是很菜啊，凑活看吧。。。）

 

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#define inf 0x3f3f3f3f
#define node pair<long long,int>
using namespace std;

/*struct node
{
    int y;
    long long l;
}s[100005];
*/
/*int cmp(node a,node b)
{
    return a.l<b.l;
}*/

int main()
{
    int n;
    long long a[100005];
    long long b[100005];
    int x[100005];
    cin>>n;
    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);
    priority_queue< node,vector<node>,greater<node> >q;


    for(int i=0;i<n;i++)
    {
        //s[i].l=a[0]+b[i];
        //s[i].y=i;
        //x[s[i].y]=0;
        q.push(make_pair(a[0]+b[i],i));
        x[i]=0;
    }
    int nn=n;
    while(nn--)
    {
        cout<<q.top().first;
        int l=q.top().second;
        q.pop();
        x[l]++;
        if(n!=0)
            cout<<" ";
        q.push(make_pair(a[x[l]]+b[l],l));
        //cout<<a[x[s[0].y]]<<"+"<<b[s[0].y]<<endl;
        /*node g;
        g.l=inf;
        int num=0;
        for(int i=0;i<n;i++)
        {
            if(s[i].l<g.l)
            {
                g=s[i];
                num=i;
            }
        }
        if(num!=0)
        {
            swap(s[0],s[num]);
        }*/
    }
    cout<<endl;
    return 0;
}