526互联

Educational Codeforces Round 155 (Rated for Div. 2) B. Chips on the Board

发布时间 2023-10-16 20:54:02作者: zsxuan

给一个 \(n \times n\) 的棋盘，和两个大小为 \(n\) 的 \(a\) \(b\) 数组。\(a_i\) 代表第 \(i\) 列的权值，\(b_i\) 代表第 \(i\) 列的权值。坐标 \((i, j)\) 的权值为 \(a_i + b_j\) 。

现在需要放若干个芯片和到棋盘上，满足以下条件：

  • 对于任意坐标 \((i, j)\) ，第 \(i\) 行或第 \(j\) 列存在一个芯片。

需要放入满足条件的若干芯片后，芯片所在位置的权值和最小。

若要使任意坐标 \((i, j)\) ，第 \(i\) 行或第 \(j\) 列存在一个芯片。则应满足：

  • 要么每行至少存在一个芯片，要么每列至少存在一个芯片。
    • 证明：显然这种情况满足条件，如果再减少一个芯片，便会存在一个位置 \((i, j)\) ，该行和该列上都没有芯片。

于是对两种情况取最小值即可。假设最小的行权值为 \(mia\) ，最小的列权值为 \(mib\) 。答案为 \(ans = min(\sum_{i=1}^{n} a_i + n \cdot mib, \sum_{i=1}^n b_i + n \cdot mia)\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n+1), b(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	for (int i = 1; i <= n; i++) std::cin >> b[i];
	int mia = *std::min_element(a.begin() + 1, a.end());
	int mib = *std::min_element(b.begin() + 1, b.end());
	ll ans1 = 1LL * mib * n; for (int i = 1; i <= n; i++) ans1 += a[i];
	ll ans2 = 1LL * mia * n; for (int i = 1; i <= n; i++) ans2 += b[i];
	std::cout << std::min(ans1, ans2) << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}