题解 | #dd爱矩阵#

算法进阶指南 例题 改编。
思路（来自 算法进阶指南 一书）：

• 假设我们只有两行 a，b 需要被合成
  • 排序
  • 最大值显然是 a[n] + b[n] ，记录最大值
  • 次大值可能出现在 a[n - 1] + b[n] 和 a[n] + b[n - 1] 之中
  • ……（自己写两个数组同上分析）
  • 我们发现，对于任意的 a[x] + b[y] 若其没有被取走那么：所有的 yy < y ，a[x] + b[yy] 必不可能是当前形势下的最大值（对 x 的分析相同）
  • 也就是说对于任意的 a[x] + b[y] 若其被取走，那么就会解锁 a[x - 1] + b[y] 和 a[x] + b[y - 1] 而我们只关注这里面的最大值，故采用二叉堆维护再好不过了。
  • 具体实现起来我们发现如果没有按上式进行拓展我们会发现很多的重复元素（这样不好），这里我采取的是一个大佬 AC 代码里的做法（多看看还是有好处的）：将数对 {1, 1}、{1, 2}、{1, 3}……都入堆，这样以后需要调整的时候就只需要调整第一维的大小就可以了，非常简洁易懂。
• 回到我们具体的问题，其实这个问题已经被解决了，只需要每次求两列数的前 n 大然后递推到最后一列答案就出来了

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define intmax 0x7fffffff
#define halfintmax 0x3fffffff

typedef pair<int, int> pii;
typedef pair<int, char> pic;

const int N = 509;
const int mod = 1e9 + 7;

int n, a[N], ans[N];

priority_queue <pii> pq;

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> ans[i];
    sort(ans, ans + n);  /// sort 默认排序从小到大，所以我的代码中并不是从 1 开始的。
    for(int i = 1; i < n; i ++) {
        for(int j = 0; j < n; j ++) cin >> a[j];
        sort(a, a + n);
        for(int i = 0; i < n; i ++)
            pq.push({ans[i] + a[n - 1], n - 1});
        int t = n - 1;
        while(~t) {
            pii pi = pq.top(); pq.pop();
            ans[t --] = pi.first;
            if(pi.second)
                pq.push({pi.first - a[pi.second] + a[pi.second - 1], pi.second - 1});
        }
        while(!pq.empty()) pq.pop();
    }
    for(int i = n - 1; ~i; i --) cout << ans[i] << ' ';
    return 0;
}