CF1859B 题解

题意

给定 \(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; 
}