题目描述
YYH手上有n盒积木，每个积木有个重量。现在他想从每盒积木中拿一块积木，放在一起，这一堆积木的重量为每块积木的重量和。现在他想知道重量最少的k种取法的重量分别是多少。
输入输出格式
输入格式：
第一行输入一个整数T，表示有T组数据
每组数据的第一行输入两个整数，n,k，意义如题目所描述。
每组数据接下来的n行，第一个整数为mi，表示第i盒积木的数量，在同一行有mi个整数，分别表示每个积木的重量
输出格式：
输出T行，分别为每组数据的答案
首先我们看到这道题的范围，就发现这是一道神奇的题目
DP？那么必须要滚动数组存储状态，不然肯定MLE，
还有没有更简单的做法？
很明显，我们需要维护一个数列的最小的前k个数，有没有什么奇特的数据结构可以帮到我们？
事实上是有的：
TOP1:堆
TOP2：优先队列。
显然，在代码长度允许的情况下，我们肯定选择好打的，（事实证明优先队列会TLE？）
我们将一个盒子的每一个数加上原来的状态（这里需要用到滚动数组存储状态）放入一个堆中，然后如果堆中已有k个元素，就判断是否比最后一个元素大，如果更大，那么就pop第一个元素，再将这个数push进去
然后就能飞快的做出答案啦！
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; int h[2][101],len[2],num[101]; int n,k,t,f,m; bool cmp(int a,int b){return a<b;} int main(){ scanf("%d",&t); for(int i=1;i<=t;i++) { memset(h,0,sizeof(h)); len[0]=1;f=0; scanf("%d%d",&n,&k); for(int j=1;j<=n;j++) { len[(f^=1)]=0; scanf("%d",&m); for(int kq=1;kq<=m;kq++) { scanf("%d",&num[kq]); for(int l=1;l<=len[f^1];l++) { int tmp=num[kq]+h[f^1][l]; if(len[f]<k) { h[f][++len[f]]=tmp; push_heap(h[f]+1,h[f]+len[f]+1,cmp); } else if(h[f][1]>tmp) { pop_heap(h[f]+1,h[f]+len[f]+1,cmp); h[f][len[f]]=tmp; push_heap(h[f]+1,h[f]+len[f]+1,cmp); } } } } sort(h[f]+1,h[f]+len[f]+1); for(int i=1;i<=k;i++) { printf("%d%c",h[f][i],(i==k)?' ':' '); } } return 0; }