poj_2442_Sequence_堆

lzusa 发布于 2019-04-22 2 次阅读


题目大意

给定n组数,每组数有若干个数组,在每一个数组中取一个数然后构成新的数组,求新数组里的值的总和最小的前m个

思路

先将第一组数存到一个数组中,然后将后面数组中的数加上第一组数的第一个后存入堆中(全部数组按升序排列)然后枚举两个数组中的值,和堆顶进行判断,如果小于堆顶就把堆顶替换掉,最后将堆里的值覆盖掉第一个数组,继续操作直至全部处理完,输出堆中的值
O(n*n*logn)

#include 
#include 
#include 
using namespace std;
int arr1[1000000],arr2[1000000];
bool cam(int x,int y)
{
    return x heap;
int main()
{
    int n,m,x;
    scanf("%d",&x);

    for (int o=1;o<=x;o++)
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=m;i++)
            scanf("%d",&arr1[i]);
        sort(arr1+1,arr1+m+1,cam);
        for (int i=2;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
                scanf("%d",&arr2[j]);
            sort(arr2+1,arr2+m+1,cam);
            for (int j=1;j<=m;j++)
            {
                int 
                    ll=arr1[1]+arr2[j];
                heap.push(arr1[1]+arr2[j]);
            }
            for (int j=2;j<=m;j++)
            {
                for (int k=1;k<=m;k++)
                {
                    int t=arr1[j]+arr2[k];
                    if (t
]]>