一系列 \(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;
}
- Codeforces Arrays Round Olya Gamecodeforces arrays round olya codeforces imbalanced arrays round codeforces round game rows codeforces round game 912 codeforces round digit game elimination technocup arrays round codeforces different arrays 1783d codeforces infinite 1785e game codeforces 1747c swap game 题解p9580 round game