POJ 2442 Sequence（stl+优先队列||堆）-蒲公英云

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

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

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;
}