【POJ 2442】 Sequence

【题目链接】
【算法】
堆
【代码】
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

#include <stack>

#include <limits.h>

using namespace std;

#define MAXM 110

#define MAXN 2010

int T,n,m,i,j;

int a[MAXM][MAXN],ans[MAXN];

struct info

{

        int p,q,val;

        bool last;

        friend bool operator < (info a,info b)

        {

                return a.val > b.val;

        }

} ;

inline void _merge(int *a,int *b)

{

        int i,j;

        priority_queue< info > q;

        static int res[MAXN];

        info tmp;

        while (!q.empty()) q.pop();

        q.push((info){,,a[]+b[],false});

        for (i = ; i <= n; i++)

        {

                tmp = q.top();

                q.pop();

                res[i] = tmp.val;

                q.push((info){tmp.p,tmp.q+,a[tmp.p]+b[tmp.q+],true});

                if (!tmp.last) q.push((info){tmp.p+,tmp.q,a[tmp.p+]+b[tmp.q],false});

        }

        for (i = ; i <= n; i++) a[i] = res[i];

}

int main()

{

        scanf("%d",&T);

        while (T--)

        {

                scanf("%d%d",&m,&n);

                for (i = ; i <= m; i++)

                {

                        for (j = ; j <= n; j++) scanf("%d",&a[i][j]);

                        sort(a[i]+,a[i]+n+);

                }

                for (i = ; i <= n; i++) ans[i] = a[][i];

                for (i = ; i <= m; i++) _merge(ans,a[i]);

                for (i = ; i < n; i++) printf("%d ",ans[i]);

                printf("%d\n",ans[n]);

        }

        return ;

}