题意
给定 \(n\) 个长度为 \(m\) 的数组，每个数组可以向别的数组转移最多一个数字，任意一个数组都可以接受无穷多的数字，最大化每个数组的最小值之和。
做法
考虑贪心。
我们记第 \(i\) 个数组的第 \(j\) 个数字为 \(a_{i, j}\)。
我们先对每一个数组按照升序进行排序，那我们最不愿意看到的就是 \(a_{i, 1}\)，因为整个数组的最小值取决于 \(a_{i, 1}\)。
那我们就把 \(n\) 个数组的最小值全部转移到一个数组里面去，假如这个“受害者”是第 \(r\) 个数组 \(a_r\)，让它保存所有的最小值 \(a_{i, 1}\)。
这样就让除 \(a_r\) 以外的数组的第 \(2\) 项 \(a_{i, 2}\) 重见光明。
那我们也要榨干第 \(2\) 项，所以我们选择第 \(2\) 项最小的数组作为 \(a_r\)。
最后计算结果为 \(\min\limits_{i = 1}^{n}a_{i, 1} + \sum\limits_{i = 1}^{sz[i]}[i \ne r]a_{i, 2}\)。
可以证明这是最优解。
代码
注意要开 long long。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 25010;
int n;
vector<int> a[N];
void solve() {
cin >> n;
int minn = 0x3f3f3f3f3f3f3f3f, mins = 0x3f3f3f3f3f3f3f3f, ans = 0;
for (int i = 1; i <= n; i++) {
int sz;
cin >> sz;
a[i].resize(sz);
for (int& x : a[i]) cin >> x;
sort(a[i].begin(), a[i].end());
minn = min(minn, a[i][0]);
mins = min(mins, a[i][1]);
ans += a[i][1];
}
ans += minn;
ans -= mins;
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}