一系列 \(n\) 个数组，第 \(i\) 个数组的大小 \(m_i \geq 2\) 。第 \(i\) 个数组为 \(a_{m_1}, a_{m_2}, \cdots, a_{m_i}\) 。
对于每个数组，你可以移动最多一个元素到另一个数组。
一系列 \(n\) 个数组的 \(beauty\) 定义为 \(\sum_{i=1}^{n} min_{j=1}^{m_i} a_{i, j}\) 。询问你经过若干操作后能够使这系列数组得到的最大美丽值，
一： \(min_{j=1}^{m_i} a_{i, j}\) 一定会对 \(beauty\) 产生贡献。假设是第 \(p\) 个数组。
二：除了第 \(p\) 个数组，所有数组都可以对 \(beauty\) 贡献次小值，然后将最小值移到数组 \(p\) 。\(min\ a_p\) 不会更小。
设第 \(i\) 个数组的最小值为 \(m1_i\) ，次小值为 \(m2_i\) 。
于是答案为 \(ans = \sum_{i=1}^{n} m2_i - min_{i=1}^{n} m2_i + min_{i=1}^{n} m1_i\) 。
view
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
int n; std::cin >> n;
ll ans = 0;
int mi_m1 = 1 << 30, mi_m2 = 1 << 30;
for (int i = 1; i <= n; i++) {
int m; std::cin >> m;
int m1 = 1 << 30, m2 = 1 << 30;
for (int i = 1; i <= m; i++) {
int x; std::cin >> x;
if (x <= m1) m2 = m1, m1 = x;
else if (x <= m2) m2 = x;
}
mi_m1 = std::min(mi_m1, m1);
mi_m2 = std::min(mi_m2, m2);
ans += m2;
}
std::cout << ans - mi_m2 + mi_m1 << "\n";
}
int main() {
int _ = 1; std::cin >> _;
while (_--) {solve();}
return 0;
}