首页 > 代码库 > POJ 2442 Sequence【堆】

POJ 2442 Sequence【堆】

题目链接:http://poj.org/problem?id=2442

题目大意:给出一个m*n的矩阵,从每一行中取出一个数相加,能得到n^m个不同的结果,要求输出其中前n项。

建立一个以n元数组为底层数组的堆,在这里,利用stl中的make_heap,pop_heap,push_heap等函数解决。

1.将第一组数据输入arr1数组,升序排序。

2.将接下来的数据输入到arr2数组中,并且heap[i]=arr1[0]+arr2[0...n-1],make_heap(heap,heap+n).

3.arr1数组从1到n-1,比较temp=arr1[i]+arr2[0...n-1]与堆顶的元素,如果temp比较小,则将堆顶元素pop,添加temp到heap;否则跳出循环。

4.将heap中的元素全部赋值给arr1数组,升序排序,重复2,3两步,直到所有数据全部处理完。

代码:

#include <iostream>
#include <cstdio>
#include <algorithm>
#define M 111
#define N 2111
using namespace std;
int arr1[N],arr2[N],heap[N];
int m,n;
int main()
{
    int t;
    bool s=true;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<n;i++)
            scanf("%d",&arr1[i]);
        sort(arr1,arr1+n);
        for(int i=1;i<m;i++)
        {
            for(int j=0;j<n;j++)
                scanf("%d",&arr2[j]);
            sort(arr2,arr2+n);
            for(int j=0;j<n;j++)
                heap[j]=arr1[0]+arr2[j];
            make_heap(heap,heap+n);
            for(int j=1;j<n;j++)
            {
                for(int k=0;k<n;k++)
                {
                    int temp=arr1[j]+arr2[k];
                    if(temp<heap[0])
                    {
                        pop_heap(heap,heap+n);//将heap里的最大值放在最后,并且重新修正heap
                        heap[n-1]=temp;
                        push_heap(heap,heap+n);
                        s=false;
                    }
                    else
                        break;
                }
                if(s)
                    break;
            }
            for(int j=0;j<n;j++)
                arr1[j]=heap[j];
            sort(arr1,arr1+n);
        }
        for(int i=0;i<n;i++)
            printf("%d ",arr1[i]);
        printf("\n");
    }
    return 0;
}