POJ 2442 Sequence

Pro. 1

给定k个有序表，取其中前n小的数字。组成一个新表，求该表？

算法：

由于 a1[1] < a1[2] < a1[3] ... <a1[n]

a2[1] < a2[2] < a2[3] ... < a2[n]

.........

ak[1] < ak[2]<ak[3]...... < ak[n]

首先每个有序表的第一个元素入堆，然后最小元素出堆。该元素入新表L，相应线性表的下一个元素入堆。

例如：如果出堆得是a2[2],那么a2[3]入堆。所以给每一个表增设一个标记。循环n次得到新表.

Pro. 2

给定两个长为n的有序表A,B，根据两表中任意两元素和得到一个大小为N^2的表，得到的新表的前n小的元素。（HDU上的一个。但是那个题目直接Hash做）

根据题意：

A[1] + B[1] < A[1] + B[2] .. < A[1] + B[n]

A[2] + B[1] < A[1] + B[2] .. < A[1] + B[n]

.......

A[n] + B[1] < A[1] + B[2] .. < A[1] + B[n]

这样就得到了n个有序表。转化为pro 1 得到答案

Pro. 3

说到正题了。给定m 个长为n 的有序表。每个表取一个元素。得到m个元素。求和。要求，求前n小的和。

每次考虑两个表，根据 a[1][1 ...n] 与a[2][1...n] ，转化为pro.2 。求出一个大小为n的表 L

再考虑表Ｌ与a[3][1...n] 得到新的表L'

接着考虑a[4][1....n]

...... 最后得到的本题的答案

Sequence

Time Limit: 6000MS		Memory Limit: 65536K
Total Submissions: 6259		Accepted: 1953

Description

Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It's clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?

Input

The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000.

Output

For each test case, print a line with the smallest n sums in increasing order, which is separated by a space.

Sample Input

1
2 3
1 2 3
2 2 3

Sample Output

3 3 4

Source

POJ Monthly,Guang Lin

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

using namespace std;

int t,n,m,A[2222],Q[2222];

struct node
{
    int arr,id;
    bool operator < (const node b) const
    {
        return arr>b.arr;
    }
};

int matrix[2222][2222];

void fuuuuuc()
{
    int cur=0;
    int nowfrom[2222];
    memset(nowfrom,0,sizeof(nowfrom));
    priority_queue<node> q;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            matrix[i][j]=Q[i]+A[j];
            if(j==0)
            {
                node x;
                x.arr=matrix[i][0]; x.id=i;
                q.push(x);
            }
        }
    }
/*
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            cout<<matrix[i][j]<<" ";
        }
        cout<<endl;
    }
*/
    for(cur=0;cur<n;cur++)
    {
        node u=q.top();  q.pop();
     //   cout<<" -->: "<<u.id<<" "<<u.arr<<endl;
        int ID=u.id;
        Q[cur]=u.arr;
        nowfrom[ID]++;
        u.arr=matrix[ID][nowfrom[ID]];
        q.push(u);
    }
}

int main()
{
    int T;
    scanf("%d",&T);
while(T--)
{
    scanf("%d%d",&m,&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&Q[i]);
    }
    sort(Q,Q+n);
    for(int i=1;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",A+j);
        }
        sort(A,A+n);
        fuuuuuc();
    }
    for(int i=0;i<n;i++)
    {
        if(i) putchar(' ');
        printf("%d",Q[i]);
    }
    putchar(10);
}
    return 0;
}

* This source code was highlighted by YcdoiT. ( style: Codeblocks )