题解 P1631 【序列合并】

ysner · 2017-07-24 12:02:07 · 题解

首先声明，我想发题解是因为我觉得我的代码最短、最简洁，并运用了将两个优先队列绑定起来的数据结构（pair）。

这道题和果子合并非常像，每次都是取2个最小的数，但是本题中每个数可以取多次，但是数对不能重复，但是算法还是一样的，利用优先队列.

由于本题中的数据已经排好序了，所以如果选取了坐标为i,j的两个数，那么下一次可能选i+1,j或i,j+1,这样的话由于每个数可以取多次容易重复，所以使用SET判重，这样的话由于要使用两个结构体，比较容易写错.

还有一种比较简单的方式，首先不管怎么样,A序列中的第一个数绝对要选，那么这个数可能和B序列中的任何一个数组成的数对被选，全部加入优先队列中，这样处理了i,j+1的情况，但是还有i+1,j的情况，每次输出一个和之后，将B序列中的第i个数对应的A序列中的第j个数的j++.

但是这样数对还是容易重复，怎么办呢？可以用一个数组记录一下，to[i]表示B序列中的第i个数与A序列中的第几个数相加，每次入队的时候累加to数组就不会造成重复了！

#include<cstdio>  
#include<queue>   
using namespace std;
int a[100005]={}, b[100005]={}, to[100005]={},i, n;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >q;
int main()
{
    scanf("%d", &n);
    for (i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &b[i]); to[i] = 1;
        q.push(pair<int, int>(a[1] + b[i], i));
    }
    while (n--)
    {
        printf("%d ", q.top().first);
        i = q.top().second; q.pop();
        q.push(pair<int, int>(a[++to[i]] + b[i], i));
    }
    return 0;
}