巅峰赛#29 T3 题解

Gragher

2026-01-08 22:14:08

发布于：浙江

31阅读

0回复

0点赞

发现在题目专区里发的题解不会在讨论总版里出现后我非常生气，于是有了本贴（。

原文：https://www.acgo.cn/problemset/97291/67514?tab=explanation。

~~吐槽一下，怎么必须要 AC 了才能发题解，害的我还得先登审核号把自己赛时代码拷过来。~~

我们需要充分发挥人类智慧，仔细观察样例 1 后可以发现当我们对每一行删去最小值后每一行都是一样的。
不妨大胆猜测，如果每一行不一样那么一定不行，如果每一行一样则一定为最优方案。
很显然，当每一行相同时，只需要一直做竖向操作即可，操作唯一。
然后就有以下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int n, m, a[maxn];
inline int getid(int i, int j) {
	return (i - 1) * m + j;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int mi = 1e18;
		for (int j = 1; j <= m; j++) cin >> a[getid(i, j)], mi = min(mi, a[getid(i, j)]);
		for (int j = 1; j <= m; j++) a[getid(i, j)] -= mi;
		ans += mi;
	}
	for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++)
			if (a[getid(i, j)] != a[getid(i + 1, j)]) {
				cout << "NO";
				exit(0);
			}
	int sum = 0;
	for (int i = 1; i <= m; i++) sum += a[getid(1, i)];
	cout << "YES\n" << ans + sum;
	return 0;
}

竟然 WA 了！
也是非常神奇。

然后我们动用观察力可以发现有如下 hack。

2 1
1
1

正常应该输出 1，直接竖着做一遍即可。

于是可以找到漏洞，不一样要先把每一行的最小值减去，先减每一列也行。于是我们把行列交换再做一次，两次取最小值。
有如下代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int n, m;
int a[maxn], b[maxn];
inline int getid(int i, int j) {
	return (i - 1) * m + j;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;

	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++)
			cin >> a[getid(i, j)], b[getid(i, j)] = a[getid(i, j)];
	int ansa = 0;
	for (int i = 1; i <= n; i++) {
		int mi = 1e18;
		for (int j = 1; j <= m; j++) mi = min(mi, a[getid(i, j)]);
		for (int j = 1; j <= m; j++) a[getid(i, j)] -= mi;
		ansa += mi;
	}
	int ansb = 0;
	for (int j = 1; j <= m; j++) {
		int mi = 1e18;
		for (int i = 1; i <= n; i++) mi = min(mi, b[getid(i, j)]);
		for (int i = 1; i <= n; i++) b[getid(i, j)] -= mi;
		ansb += mi;
	}
	for (int i = 1; i < n; i++) for (int j = 1; j <= m; j++)
			if (a[getid(i, j)] != a[getid(i + 1, j)]) {
				cout << "NO";
				exit(0);
			}
	for (int j = 1; j <= m; j++) ansa += a[getid(1, j)];
	for (int i = 1; i <= n; i++) ansb += b[getid(i, 1)];
	cout << "YES\n" << min(ansa, ansb);
	return 0;
}