Gym 101116A Assembly Required 【思维】

传送门：Gym 101116A

---

Assembly Required

Princess Lucy broke her old reading lamp, and needs a new one. The castle orders a shipment of parts from
the Slick Lamp Parts Company, which produces interchangable lamp pieces.
There are m types of lamp pieces, and the shipment contained multiple pieces of each type. Making a lamp
requires exactly one piece of each type. The princess likes each piece with some value, and she likes a lamp
as much as the sum of how much she likes each of the pieces.
You are part of the castle staff, which has gotten fed up with the princess lately. The staff needs to propose
k distinct lamp combinations to the princess (two lamp combinations are considered distinct if they differ
in at least one piece). They decide to propose the k combinations she will like the least. How much will the
princess like the k combinations that the staff proposes?

Input
The first line of input contains a single integer T (1 ≤ T ≤ 10), the number of test cases. The first line of each test case contains two integers m (1 ≤ m ≤ 100), the number of lamp piece types and k (1 ≤ k ≤ 100), the number of lamps combinations to propose. The next m lines each describe the lamp parts of a type;
they begin with ni (2 ≤ ni ≤ 100), the number of pieces of this type, followed by ni ntegers vi,1, . . . , vi,ni
(1 ≤ vi,j ≤ 10,000) which represent how much the princess likes each piece. It is guaranteed that k is no greater than the product of all ni’s.

Output
For each test case, output a single line containing k integers that represent how much the princess will like the proposed lamp combinations, in nondecreasing order.

Sample Input
2
2 2
2 1 2
2 1 3
3 10
4 1 5 3 10
3 2 3 3
5 1 3 4 6 6

Sample Output
2 3
4 5 5 6 6 7 7 7 7 7

Explanation
In the first case, there are four lamp pieces, two of each type.
The worst possible lamp has value 1 + 1 = 2,
while the second worst possible lamp has value 2 + 1 = 3.

---

题意：
第一行一个样例数T
第二行 m 和 k
接下来是m行 第一个数字n 表示这行有n个数
要求从每行选一个数求和
求前k个最小的数

题解：
如果直接把所有情况都算出来，最后排序取前k个，那么一定会超时。
我们可以一行一行求，把这一行的每个数字加上上一行求出来的前k个最小的数，
然后取前k个最小的存下来，给下一行做准备就行。
(本来准备用优先队列做的，但是感觉太麻烦了= _ =)

---

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=100005;
int t,m,k,n;
//priority_queue<int> q;
int a[N];
int sum[N];
int main()
{
  int x;
  scanf("%d",&t);
  while(t--)
  {
    memset(sum,0,sizeof(sum));
    scanf("%d%d",&m,&k);
    int ans=1;
    for(int i=0;i<m;i++)
    {
      int len=0;
      scanf("%d",&n);
      for(int j=0;j<n;j++)
      {
        scanf("%d",&x);
        for(int z=0;z<ans;z++)
        {
          a[len++]=x+sum[z];//输入的数加上上一行的前k个数
        }
      }
      sort(a,a+len);//排序取前k个
      for(int j=0;j<k;j++)
      {
        sum[j]=a[j];//记录上一行的值
      }
      ans=min(k,len);
    }
    for(int i=0;i<k;i++)
    {
      printf("%d%c",a[i],i==k-1?'\n':' ');
    }
  }
  return 0;
}