1504: ZZ的橱柜（优先队列）

1504: ZZ的橱柜

http://www.acmore.net/problem.php?id=1504

Time Limit: 1 Sec Memory Limit: 64 MB
Submit: 315 Solved: 38

Description

ZZ不仅喜欢买衣服，还是个吃货，天哪！现在的妹纸是怎么了？╮(╯_╰)╭，ZZ有两个大型橱柜A和B，里面放满了零食,每个橱柜里面有N个方格，每个方格里面放了不同重量的美味，现在ZZ要从A、B里面各取一个方格的美味，可是ZZ不想变得太胖，于是他会尽量的选择重量少的美味，当然不是所有的组合都是ZZ喜欢吃的美味，所以她想了一个特别的方法，他会选出组合重量最小的前M种中选出一种，可是怎么才能算出前M个组合的重量的呢？这个真是个难题，作为ACMer的ZZ竟然不能解决，你能帮帮她么？

Input

有多组测试数据;

第一行给你一个N(N<=400000)和一个M(M<=N)，N表示每个壁橱有N个方格,M表示要选出M种方案；

第二行和第三行分别有N个整数，表示每个方格的美味重量(结果保证在int以内)

Output

按照从小到大的顺序输出前M种方案的重量，每种方案占一行

Sample Input

2 2 1 2 3 4

Sample Output

4 5

HINT

Source

2013ACM多校联合(4)_NUN

从小到大排完序之后，就成了两个有序表的前N 个最小和。

我们可以把这些看成n 个有序表：

A[1]+B[1]<=A[1]+B[2]<=A[1]+B[3]……..

A[2]+B[1]<=A[2]+B[2]<=A[2]+B[3]……..
……..

A[n]+B[1]<=A[n]+B[2]<=A[n]+B[3]……..

然后用一个优先队列来维护，队列中始终保持有 n 个元素，每次取出最小的元素，把对应的有序表(以上不等式中的)后一个元素加入队列。

一共输出n 个元素，时间复杂度为O(n),空间复杂度为O(n).

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>

using namespace std;

const int N=400010;

int n,m;
int a[N],b[N];

struct node{
    int x,y;
    int num;
    bool operator < (const node &a) const{
        return a.num<num;
    }
};

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=0;i<n;i++)
            scanf("%d",&b[i]);
        sort(b,b+n);
        priority_queue<node> q;
        node cur,next;
        for(int i=0;i<m;i++){
            cur.x=i,    cur.y=0,    cur.num=a[i]+b[0];
            q.push(cur);
        }
        int cnt=m;
        while(cnt>0){
            cur=q.top();
            q.pop();
            printf("%d\n",cur.num);
            cnt--;
            next.x=cur.x,   next.y=cur.y+1,     next.num=a[next.x]+b[next.y];
            q.push(next);
        }
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>

using namespace std;

const int INF=0x3f3f3f3f;
const int N=400010;

int a[N],b[N];
int n,m;

struct node{
    int x,y;
    int val;
    node(){}
    node(int xx,int yy,int v):x(xx),y(yy),val(v){}

    bool operator < (const node &a) const{
        return a.val<val;
    }
};

int main(){

    //freopen("input.txt","r",stdin);

    while(~scanf("%d%d",&n,&m)){
        for(int i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=0;i<n;i++)
            scanf("%d",&b[i]);
        sort(b,b+n);

        node tmp;
        priority_queue<node> q;
        for(int i=0;i<n;i++)
            q.push(node(i,0,a[i]+b[0]));
        int cnt=0;
        while(cnt<m){
            tmp=q.top();
            q.pop();
            printf("%d\n",tmp.val);
            q.push(node(tmp.x,tmp.y+1,a[tmp.x]+b[tmp.y+1]));
            cnt++;
        }
    }
    return 0;
}