POJ 2442 Sequence（stl+优先队列||堆）

淩亂°似流年 2022-06-10 07:29 226阅读 0赞

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

题解：

题意：

给n个数列，长度都为m，一共m次让你每次从各个数列中选一个数组相加成新的数列，让你求该数列的前n小的值

思路：

首先将给的第一行的数为初始数，每次求前一行（这里的前一行代表是前面所有行的前n小和）与后一行和的前n小的值，遍历完所有行，最后输出就是结果

优先队列代码，时间耗得比堆的写法要多一点：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    #define INF 100861111;
    using namespace std;
    int a[2005];//存前几行的前n小和
    int b[2005];//存当前行的值
    priority_queue<int>q;//相当于一个最大堆
    int main()
    {
        int i,j,k,n,m,t,s,ans;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&m,&n);
            s=0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            sort(a,a+n);//排序
            for(i=1;i<m;i++)
            {
                for(j=0;j<n;j++)
                {
                    scanf("%d",&b[j]);
                    q.push(a[j]+b[0]);//将之前每一项与第一项的加作为初始的前n小项进行更新
                }
                for(j=1;j<n;j++)//对每一个当前数组值进行遍历更新
                {
                    for(k=0;k<n;k++)//遍历相加所有的前n项
                    {
                        int x=a[k]+b[j];
                        if(x>=q.top())//如果当前和比最大堆堆顶都大就不用加下去了
                            break;
                        q.pop();
                        q.push(x);//更新堆顶
                    }
                }
                int ans=n-1;//如果要最小的在前要从后往前插入
                while(!q.empty())
                {
                    a[ans]=q.top();
                    q.pop();
                    ans--;
                }
            }
            printf("%d",a[0]);
            for(i=1;i<n;i++)
                printf(" %d",a[i]);
            printf("\n");
        }
        return 0;
    }

还有就是用make\_heap的做法，会比优先队列快一些。。这个是学别人的，实现原理和上面相同只是用的STL工具不同，就不打代码了

然后补充一点关于这个的小知识：

make\_heap(a，a+n）a可以是任何类型的数组，用来建堆，不过如果不是基础类型的话就要重载小于号，基础类型不重载默认为最大堆，a\[0\]就为堆顶，a\[n-1\]为末尾

用push\_heap（a,a+n）作用就是更新堆

pop\_heap(a,a+n)作用是将堆顶移到堆的尾部就是a\[n-1\]处，其他地方保持堆的形状，这些东西如果不是堆就不能用

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<deque>
    #define M (t[k].l+t[k].r)/2
    #define lson k*2
    #define rson k*2+1
    #define ll long long
    #define INF 100861111;
    using namespace std;
    int a[2005];
    int b[2005];
    int tem[2005];
    int main()
    {
        int i,j,k,n,m,t,s,ans;
        scanf("%d",&t);
        while(t--)
        {
            scanf("%d%d",&m,&n);
            s=0;
            for(i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            sort(a,a+n);
            for(i=1;i<m;i++)
            {
                for(j=0;j<n;j++)
                {
                    scanf("%d",&b[j]);
                    tem[j]=a[j]+b[0];
                }
                make_heap(tem,tem+n);
                for(j=1;j<n;j++)
                {
                    for(k=0;k<n;k++)
                    {
                        int x=a[k]+b[j];
                        if(x>=tem[0])
                            break;
                        pop_heap(tem,tem+n);
                        tem[n-1]=x;
                        push_heap(tem,tem+n);
                    }
                }
                sort(tem,tem+n);
                for(j=0;j<n;j++)
                    a[j]=tem[j];
            }
            printf("%d",a[0]);
            for(i=1;i<n;i++)
                printf(" %d",a[i]);
            printf("\n");
        }
        return 0;
    }