【POJ 2442】Sequence

【POJ 2442】Sequence

优先队列 m个序列 每个序列n个数 从每个序列中取一个数 可以组成一个长为m的序列 这样一共有n^m种组法 把所有组合的加和排序后输出前n小的和

乍一看听高深的一个问题 其实想清楚了很简单
每一组中取一个数相加 第一组可以有n种取法
假设当前只有两组 按题意组合就是将第一组中n个数分别与第二组n个数相加 取出前n小的和

那么现在再来一组 前两组一共有n*n种组合 每种组合与第三组中n个数再组合 前n小的和就是结果 这三组一共有n^3种组合 然而答案只需要前n小的 其实前两组组合后得到的n*n组中 只有前n小的组合对第三组的答案有贡献

由上可知 每增加一列 只需组合出前n小的组合即可 这样我们只需准备一个递减队列 一个递增队列 每加入一组 不断从递增队列中提出队首与加入的n个数组合 每组合一次 假如递减队列还未加数 直接加入 如果递减队列已经有n个数 呢么将组合出的数与递减队列对首(队列中最大值)比较 如果比队首小 将他替换 否则扔掉 每组组合结束后 把递减队列全部转换到递增队列中 为下一组组合或者输出答案做准备

代码如下:

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

using namespace std;

priority_queue <int,vector<int>,greater<int> > d;
priority_queue <int,vector<int>,less<int> > q;
int num[2001];

int main()
{
    int t,m,n,i,j,x;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d %d",&m,&n);

        for(i = 1; i <= n; ++i)
        {
            scanf("%d",&x);
            d.push(x);
        }

        for(i = 1; i < m; ++i)
        {
            x = d.top();
            d.pop();
            for(j = 1; j <= n; ++j)
            {
                scanf("%d",&num[j]);
                if(q.size() < n)
                {
                    q.push(x+num[j]);
                }
                else if(num[j]+x < q.top())
                {
                    q.pop();
                    q.push(x+num[j]);
                }
            }
            while(!d.empty())
            {
                x = d.top();
                d.pop();
                for(j = 1; j <= n; ++j)
                {
                    if(q.size() < n)
                    {
                        q.push(x+num[j]);
                    }
                    else if(num[j]+x < q.top())
                    {
                        q.pop();
                        q.push(x+num[j]);
                    }
                }
            }
            while(!q.empty())
            {
                d.push(q.top());
                q.pop();
            }
        }
        for(i = 1; i < n; ++i)
        {
            printf("%d ",d.top());
            d.pop();
        }
        printf("%d\n",d.top());
        d.pop();
    }
    return 0;
}