Zznu 1913: yifan and matrix (多路归并)

题目链接：

　　1913: yifan and matrix

题目描述：

　　有一个n*n的矩阵，在每一行取出一个数，可以得到n个数的和，问前n小的和分别是多少？

解题思路：
　　对于两个数组a[n],b[n]，我们可以用二路归并维护一个升序序列a[i]+b[j](1<=i<=n,1<=j<=n)，先把a[i]+b[1](1<=i<=n)加进优先队列，每次取出队首元素，记录下来，然后再改变为a[i]+b[j+1]再加进队列.

依次进行n-1二路合并即可。

　　优美的代码将要闪亮登场！！！！！

 #include <queue>

 #include <cstdio>

 #include <string>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int sum, num;

     node (int a, int b):sum(a),num(b){}

     bool operator < (const node &a) const {

         return sum > a.sum;

     }

 };

 int maps[maxn][maxn], ans[maxn], arr[maxn];

 int n;

 void Merge (int cnt)

 {

     priority_queue <node> Q;

     for (int i=; i<n; i++)

         Q.push (node(ans[i]+maps[cnt][], ));

     for (int i=; i<n; i++)

     {

         node p = Q.top ();

         Q.pop();

         arr[i] = p.sum;

         if (p.num != n)

         {

             p.sum += maps[cnt][p.num+] - maps[cnt][p.num];

             p.num ++;

             Q.push (p);

         }

     }

     for (int i=; i<n; i++)

         ans[i] = arr[i];

 }

 int main ()

 {

     while (scanf ("%d", &n) != EOF)

     {

         for (int i=; i<n; i++)

         {

             for (int j=; j<n; j++)

                 scanf ("%d", &maps[i][j]);

             sort (maps[i], maps[i]+n);

         }

         for (int i=; i<n; i++)

             ans[i] = maps[][i];

         for (int i=; i<n; i++)

             Merge (i);

         for (int i=; i<n; i++)

             printf ("%d%c", ans[i], i==n-?'\n':' ');

     }

     return ;

 }

巴特西

Zznu 1913: yifan and matrix (多路归并)

最新文章

热门文章