POJ 2442-Sequence（优先队列-m组n个数每组取一个求n个最小值）

绝地灬酷狼 2022-07-11 13:45 98阅读 0赞

Sequence

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;6000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;9285</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;3097</td> 
  </tr> 
 </tbody> 
</table>

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

## 题目意思： ##

有m组序列，每组有n个数。从每组中取一个数并求和，输出最小的n个和。

## 解题思路： ##

输入一组处理一组，先求出前两组数的n个最小和，再输入一组数，将这组数与前面的n个最小和一起处理，再求出这两组数的n个最小和…………直到m组数全部输入处理完毕。

处理过程如下：

①第一组数输入A数组中后降序排列，第二组数输入B数组后也降序排列

②将A\[0\]+B\[i\]这n个数先入队，再依次遍历A数组剩下的n-1个数与B数组的n个数之和，每次比较将较小的和入队。

③遍历完毕后，将队列中元素赋给A数组，同时队列清空。

④输入下一组数到B数组，重复②，直到m组数输入处理完毕。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <queue>
    #include <algorithm>
    const int MAXN=30030;
    int a[MAXN],b[MAXN];
    using namespace std;
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin>>t;
        while(t--)
        {
            priority_queue<int>q;//最大值优先
            int m,n;
            cin>>m>>n;
            for(int i=0; i<n; ++i)
                cin>>a[i];
            sort(a,a+n);//升序排列
            --m;
            while(m--)
            {
                for(int i=0; i<n; ++i)
                    cin>>b[i];
                sort(b,b+n);
                for(int i=0; i<n; ++i)//入队
                    q.push(a[0]+b[i]);
                for(int i=1; i<n; ++i)//依次比较将较小的和入队
                    for(int j=0; j<n; ++j)
                    {
                        int temp=a[i]+b[j];
                        if(temp<q.top())
                        {
                            q.pop();
                            q.push(temp);
                        }
                    }
                for(int i=0; i<n; ++i)//将队列中的数赋给a数组，同时队列清空
                {
                    a[i]=q.top();
                    q.pop();
                }
                sort(a,a+n);
            }
            for(int i=0; i<n-1; ++i)//输出结果
                cout<<a[i]<<" ";
            cout<<a[n-1]<<endl;
        }
        return 0;
    }
    /*
    1
    2 3
    1 2 3
    2 2 3
    */

## 测试数据： ##

2
    2 3
    1 2 3
    2 2 3
    10 10
    21 12 123 3 21 123 32 143 43 56
    2 32 43 34 54 56 656 76 43 234
    234 45 5 65 56 76 43 23 435 57
    32 324 435 46 56 76 87 78 43 23
    3 32 324 45 56 57 34 23 54 565
    23 32 34 342 324 232 2 432 324 12
    234 324 4 45 65 67 435 23 5 654
    34 3245 345 56 56 657 67 456 345 325
    234 234 546 65 88 66 53 654 65 765
    5 3 34 34 34 56 345 234 2 34

## 运行结果： ##

3 3 4
    131 132 132 133 134 135 140 140 141 141

[POJ Monthly]: http://poj.org/searchproblem?field=source&key=POJ+Monthly