AcWing 146. 序列 (优先队列)

桃扇骨 2021-11-17 11:40 145阅读 0赞

给定m个序列，每个包含n个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。

很明显，我们一共可以得到nm  
个这种序列， 然后我们可以计算每个序列中的数字之和，并得到nm

个值。

现在请你求出这些序列和之中最小的n个值。  
输入格式

第一行输入一个整数T，代表输入中包含测试用例的数量。

接下来输入T组测试用例。

对于每组测试用例，第一行输入两个整数m和n。

接下在m行输入m个整数序列，数列中的整数均不超过10000。  
输出格式

对于每组测试用例，均以递增顺序输出最小的n个序列和，数值之间用空格隔开。

每组输出占一行。  
数据范围

0<m≤1000  
,  
0<n≤2000

输入样例：

1  
2 3  
1 2 3  
2 2 3

输出样例：

3 3 4

题目链接： [https://www.acwing.com/problem/content/148/][https_www.acwing.com_problem_content_148]

分析：  
我们可以先考虑两个序列的形式。  
我们可以先将两个序列按从小到大进行排序，这样的话最小的值应是a\[1\] + b\[1\]。那么第二小的值应该是a\[1\] + b\[2\] 或者 a\[2\] + b\[1\]。同理，第三小的也应该为第二小的推导可得。我们可以用优先队列来维持这个推导过程。同时，为了避免推导的时候出现重复的值 例如：（a\[2\] + b\[2\] 可以由a\[1\] + b\[2\] 或者 a\[2\] + b\[1\]推导得到。）所以，应该设立一个三元组（i,j,last），第三个last表示上一步是动的i还是j。

这个思路的代码，可是wa了。于是换了个思路

#include"stdio.h"
    #include"string.h"
    #include"queue"
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    typedef struct Node
    {
        int x,y;
        int last;
        ll weight;
        Node(int a,int b,int c,ll d)
        {
            x = a; y = b; c = last; weight = d;
        }
        bool operator < (Node a,Node b)
        {
            a.weight > b.weight;
        }
    }Node;
    
    int T,n,m;
    ll a[1010][2010];
    
    void solve(int x)
    {
        int i = 1,j = 1;
        int top = 0;
        priority_queue<Node> Q;
        Q.push({i,j,1,(ll)a[1][i] + a[x][j]});
        ll now[2010];
        while(top <= m)
        {
            Node T = Q.top(); Q.pop();
            now[++ top] = T.weight;
            if(T.last == 1)
            {
                Q.push({T.x,T.y + 1,0,(ll)a[1][T.x] + a[x][T.y + 1]});
                Q.push({T.x + 1,T.y,1,(ll)a[1][T.x + 1] + a[x][T.y]});
            }
            else
            {
                Q.push({T.x,T.y + 1,0,(ll)a[1][T.x] + a[x][T.y + 1]});
            }
        }
        for(int i = 1; i <= m; i ++)
            {
                a[1][i] = now[i];
                //printf("%lld ",now[i]);
            }
        //printf("\n");
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&n,&m);
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= m; j ++)
                    {
                        scanf("%lld",&a[i][j]);
                        //printf("%lld ",a[i][j]);
                    }
            sort(a[1] + 1,a[1] + m + 1);
            for(int i = 2; i <= n; i ++)
            {
                sort(a[i] + 1,a[i] + m + 1);
               // for(int j = 1; j <= m; j ++)
               //     printf("%lld ",a[i][j]);
               // printf("\n");
                solve(i);
            }
            for(int i = 1; i <= m; i ++)
                printf("%lld ",a[1][i]);
            printf("\n");
        }
    }

我们可以先将一个b数组里面的序列加上a\[1\]的值，全部放进优先队列中。  
然后在依次弹出并不断加入。  
如果第一次弹出了a\[1\] + b\[1\].那么我就紧跟着把a\[2\] + b\[1\]放入优先队列中。不断操作，可以得到正确答案。

#include"string.h"
    #include"algorithm"
    #include"queue"
    using namespace std;
    
    typedef struct Node
    {
        int x,y;
        int weight;
        Node(int a,int b,int d)
        {
            x = a;
            y = b;
            weight = d;
        }
        friend bool operator < (Node a,Node b)
        {
            return a.weight > b.weight;
        }
    }Node;
    struct cmp
    {
        bool operator () (const Node &a,const Node &b)
        {
            a.weight > b.weight;
        }
    };
    
    int T,n,m;
    int a[1010][2010];
    
    void solve(int x)
    {
        int i = 1,j = 1;
        priority_queue<Node > Q;
        for(int i = 1; i <= m; i ++)
        {
            Q.push({1,i,a[1][1] + a[x][i]});
        }
    
        int now[2010],top = 0;
        while(top <= m)
        {
            Node T = Q.top();
            Q.pop();
            now[++ top] = T.weight;
            Q.push({T.x + 1,T.y,a[1][T.x + 1] + a[x][T.y]});
        }
        for(int i = 1; i <= m; i ++)
            a[1][i] = now[i];
    }
    
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%d%d",&n,&m);
            for(int i = 1; i <= n; i ++)
                for(int j = 1; j <= m; j ++)
                    scanf("%d",&a[i][j]);
            sort(a[1] + 1,a[1] + m + 1);
            for(int i = 2; i <= n; i ++)
            {
                sort(a[i] + 1,a[i] + m + 1);
                solve(i);
            }
            for(int i = 1; i <= m; i ++)
                printf("%d ",a[1][i]);
            printf("\n");
        }
    }

[https_www.acwing.com_problem_content_148]: https://www.acwing.com/problem/content/148/