提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

UVA11997求前k个和，多路归并问题

归并 问题 多路
2023-09-11 14:14:00 时间
题意：
     给你一个二维矩阵，n*n的，每次从每一行中拿出来一个，然后加起来组成一个和，一共可以得到n^n个和，要求求出这n^n个和中最小的那n个和。


思路：
     多路归并问题，先说下多路归并问题，我的理解是有个变量，每个变量都按照自己的变化规律在变化着，每次一旦选用每个变量，那么这个变量就会根据自己的变化规律变化，这种问题我们可以用优先队列来解决，首先我们可以把所有变量都扔进队列，然后在在里面取出一个最小的（或者最大的）作为当前答案，然后把取出来的数值变化后在扔进队列里，如此反复操作，对于这个题目我们可以像白书上一样这样分析，首先我们想一个该问题的简化版，就是给你两个数组，每个数组里面有n个数字，每次从两个数组中任意取出一个数字加起来得到一个和，求前n个最小的和。


我们可以运用多路归并问题


A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3]...
A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3]...
A[3]+B[1] <= A[3]+B[2] <= A[3]+B[3]...
...


对于每一个集合的每一个变量我们可以这样表示，node.s = A[a] + A[b] ,node.b =b;
这样这个集合的下一个变量就是 node.s - B[node.b] + B[node.b + 1] ,node.b ++;
这样说应该没问题吧？ 然后我们就开始多路归并，很容易理解和想到，我们直接先把第一列圈放进队列，然后取出一个最为最小的那个，然后把取出的这个的右侧（下一个）放进队列，然后在取，在放，每次都把取出的下一个放进去，执行n此之后就得到了这最小的n个数，这是两个序列的，这个题目是n个序列，这样我们可以吧第一个和第二个合并，然后在用合并的序列去合并第三个，最后把所有的序列都合并，这里说的合并就是前面上多那个多路归并。






#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>


#define N 750 + 5


using namespace std;


typedef struct NODE
{
    int s ,b;
    friend bool operator < (NODE a ,NODE b)
    {
       return a.s > b.s;
    }
}NODE;


int num[N][N];
int A[N] ,B[N] ,C[N];
NODE xin ,tou;




void duoluguibing(int n)
{
    priority_queue<NODE>q;  
    for(int i = 1 ;i <= n ;i ++)
    {
       xin.b = 1;
       xin.s = A[i] + B[1];
       q.push(xin);
    }
    for(int i = 1 ;i <= n ;i ++)
    {
        tou = q.top();
        q.pop();
        C[i] = tou.s;
        xin.b = tou.b + 1;
        xin.s = tou.s - B[tou.b] + B[xin.b];
        if(xin.b <= n) q.push(xin);
    }
    return;
}


int main ()
{
    int n ,i ,j;
    while(~scanf("%d" ,&n))
    {
       for(i = 1 ;i <= n ;i ++)
       {
          for(j = 1 ;j <= n ;j ++)
          scanf("%d" ,&num[i][j]);
          sort(num[i] + 1 ,num[i] + n + 1);
       }
       
       
       for(i = 1 ;i <= n ;i ++)
       C[i] = num[1][i];
       for(i = 2 ;i <= n ;i ++)
       {
          for(j = 1 ;j <= n ;j ++)
          A[j] = C[j] ,B[j] = num[i][j];
          duoluguibing(n);
       }
       
       for(i = 1 ;i <= n ;i ++)
       if(i == n) printf("%d\n" ,C[i]);
       else printf("%d " ,C[i]);
    }
    return 0;
}
       





相关文章