YYH的积木（NOIP模拟赛Round 6）

题目描述

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[][],len[],num[];

int n,k,t,f,m;

bool cmp(int a,int b){return a<b;}

int main(){

    scanf("%d",&t);

    for(int i=;i<=t;i++)

    {

        memset(h,,sizeof(h));

        len[]=;f=;

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

        for(int j=;j<=n;j++)

        {

            len[(f^=)]=;

            scanf("%d",&m);

            for(int kq=;kq<=m;kq++)

            {

                scanf("%d",&num[kq]);

                for(int l=;l<=len[f^];l++)

                {

                    int tmp=num[kq]+h[f^][l];

                    if(len[f]<k)

                    {

                        h[f][++len[f]]=tmp;

                        push_heap(h[f]+,h[f]+len[f]+,cmp);

                    }

                    else if(h[f][]>tmp)

                    {

                        pop_heap(h[f]+,h[f]+len[f]+,cmp);

                        h[f][len[f]]=tmp;

                        push_heap(h[f]+,h[f]+len[f]+,cmp);

                    }

                }

            }

        }

        sort(h[f]+,h[f]+len[f]+);

        for(int i=;i<=k;i++)

        {

            printf("%d%c",h[f][i],(i==k)?'\n':' ');

        }

    }

    return ;

}

巴特西

YYH的积木（NOIP模拟赛Round 6）

题目描述

输入输出格式

最新文章

热门文章