526互联

Codeforces Round 872 (Div. 2) B. LuoTianyi and the Table

发布时间 2023-10-20 08:32:20作者: zsxuan

给一个 \(n \times m\) 的矩阵和 \(n \times m\) 个数，你需要把这些数填入矩阵。保证

\[\sum_{i=1}^n \sum_{j=1}^m \left ( \mathop{max}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_{x, y} - \mathop{min}\limits_{1 \leq x \leq i, 1 \leq y \leq j} a_{x, y} \right ) \]

在所有填数方案中最大。

输出这个最大值。

显然所求是所有二维前缀的最大值减去最小值之和。

不难想到：

  • 若最大值放在 \(a_{1, 1}\) ，则前缀最大值为定值。此时只需要让前缀最小值尽可能小。
    • 于是最小值和次小值在 \(a_{1, 2}\) 和 \(a_{2, 1}\) 的位置，就能取遍除 \(s_{1, 1}\) 外的前缀最小值。
  • 若最小值放在 \(a_{1, 1}\) ，则前缀最小值为定值。
    • 于是最大值和次大值在 \(a_{1, 2}\) 和 \(a_{2, 1}\) 的位置，就能取遍除 \(s_{1, 1}\) 外的前缀最大值。
  • 没有其他情况可能产生更大贡献。

不妨让 \(n \geq m\) 。设 \(mx_1, mx_2\) 为最大值和次大值，\(mi_1, mi_2\) 为最小值和次小值。

\(s_{1, 1}\) 不会产生贡献。

假设 \(a_{1, 1}\) 为最大值。则最小值要占据尽可能多的贡献，次小值占据剩下的贡献，以保证最小前缀的和最小。
则 \(min\_s_{1, 2 \sim n - 1}\) 为最小值，\(min\_s_{2 \sim m - 1, 1}\) 为次小值，\(min\_s_{2 \sim n, 2 \sim m}\) 为最小值。
\(ans_1 = (n \times m - 1) mx_1 - m (n - 1) mi_1 - (m - 1) mi_2\) 。

假设 \(a_{1, 1}\) 为最小值。则最大值要占据尽可能多的贡献，次大值占据剩下的贡献，以保证最大前缀的和最大。
则 \(max\_s_{1, 2 \sim n - 1}\) 为最大值，\(min\_s_{2 \sim m - 1, 1}\) 为次大值，\(min\_s_{2 \sim n, 2 \sim m}\) 为最大值。
\(ans_2 = m (n - 1) mx_1 + (m - 1) mx_2 - (n \times m - 1) mi_1\) 。

view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
	int n, m; std::cin >> n >> m;
	int mx1 = -1 << 30, mx2 = -1 << 30, mi1 = 1 << 30, mi2 = 1 << 30;
	for (int i = 0; i < n * m; i++) {
		int x; std::cin >> x;
		if (x > mx1) mx2 = mx1, mx1 = x;
		else if (x > mx2) mx2 = x;
		if (x < mi1) mi2 = mi1, mi1 = x;
		else if (x < mi2) mi2 = x;
	}
	if (n < m) std::swap(n, m);
	ll ans1 = 1LL * (n * m - 1) * mx1 - 1LL * m * (n - 1) * mi1 - 1LL * (m - 1) * mi2;
	ll ans2 = 1LL * m * (n - 1) * mx1 + 1LL * (m - 1) * mx2 - 1LL * (n * m - 1) * mi1;
	std::cout << std::max(ans1, ans2) << '\n';
}               
int main() { 
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}