思路与神奇操作
这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和，而次大和就是 \(n-1\)个序列的最大和 和 一个头部值最小的序列的头部值 之和。所以，我们把视野缩小一些，讨论两个序列的合并。
两个区间的最优解一定是\(a[1]与b[1]\)，当然这两个序列已经排过序了。那么次优解就是\(max\{a[1]+b[2],a[2]+b[1]\}\)。我们可以从一个最优解分裂出两个候选项。但是我们发现，如果将这个进行到第三步时，就会出一些奇奇怪怪的问题。
第三步：次次优解是\(max\{a[2]+b[2],a[2]+b[2],a[1]+b[3],a[3]+b[1]\}\)，我们发现会有两个项重复，而且在比较中只能比较两个项，所以很容易出现重复的情况。我们在这里就可以使用标题中提到的神奇操作：我们定义一个 ADT 来储存我们每个解在两个序列的偏移量和解的值，并且还要定义一个\(flag\)的布尔变量，来进行区分。因为重叠解的出现是有一定周期的（周期长度就是2次操作），所以每一次操作时碰见\(flag==true\)，就少添加一个解。如果碰上\(flag==false\)，那就果断把一个解派生成两个解。
具体的可以看看代码：
// POJ2442.cpp
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
using namespace std;
int T, m, n, seq[110][2020], seqb[2020], tmp[2020];
struct node
{
int val, l, r;
bool flag;
bool operator<(const node &nd) const
{
return val > nd.val;
}
};
int main()
{
scanf("%d", &T);
while (T--)
{
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++)
{
for (int j = 1; j <= n; j++)
scanf("%d", &seq[i][j]);
sort(seq[i] + 1, seq[i] + n + 1);
}
for (int i = 1; i <= n; i++)
seqb[i] = seq[1][i];
for (int ln = 2; ln <= m; ln++)
{
priority_queue<node> npool;
npool.push(node{seqb[1] + seq[ln][1], 1, 1, false});
int cnt = 1;
while (cnt <= n)
{
node curt = npool.top();
npool.pop();
tmp[cnt++] = curt.val;
if (!curt.flag)
npool.push(node{seqb[curt.l + 1] + seq[ln][curt.r], curt.l + 1, curt.r, false});
npool.push(node{seqb[curt.l] + seq[ln][curt.r + 1], curt.l, curt.r + 1, true});
}
for (int i = 1; i <= n; i++)
seqb[i] = tmp[i];
}
for (int i = 1; i <= n; i++)
printf("%d ", seqb[i]);
printf("\n");
}
return 0;
}