周黑鸭（a）

题目描述

给两个\(n×m\)的矩阵A和B，你可以进行若干次操作。每次操作你可以使A或B的某一行或者某一列的所有元素增加1。
问至少要多少次操作，才能使A和B相等。

输入格式

从文件a.in中读入数据。
第一行一个正整数T，表示数据组数。
每组数据的第一行两个正整数n,m。
接下来n行，每行m个非负整数\(A_{i,j}\)，表示矩阵A。
接下来n行，每行m个非负整数\(B_{i,j}\)，表示矩阵B。

输出格式

输出到文件a.out中。
对于每组数据，输出一行一个整数表示答案。如果无论怎么操作都不能使得A和B相等，输出−1。

解析

用到数学代换比较多，首先B矩阵加相当于A矩阵减，所以我们只关心A矩阵的变化。
设A第i行需要增加\(r_i\),第i列需要增加\(c_i\)，我们的目标是求最小的\(\sum|r_i| + \sum|c_i|\)。
设\(r_1 = x\),通过第一行的信息可以得到\(c_i = B_{1, i} – A_{1, i} – x\)，通过第一列得到\(r_i = B_{i,1} – A_{i,1} – B_{1,1}+A_{1,1} + x\)。
有一个显然的性质\(A_{i,j} + r_i + c_j = B_{i,j}\)，通过此判断无解情况。
最后要求形如\(\sum_{i = 1} ^ {n + m} |x – a _ i|\)的形式（注意只是形如）,那么通过数学可以知道x取a的中位数的答案最小。

代码

#include <bits/stdc++.h>
#define ll long long
#define eb emplace_back
using namespace std;
const int N = 1e5 + 10;
int T, n, m;
ll a[N], b[N];
int id(int x, int y) {return (x - 1) * m + y;}
void solve() {
	ll ans = 0;
	vector<ll> vec;
	cin >> n >> m;
	for (int i = 1; i <= n * m; i ++) cin >> a[i];
	for (int i = 1; i <= n * m; i ++) {
		cin >> b[i]; a[i] = b[i] - a[i];
	}
	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			if (a[id(i, j)] != a[id(1, j)] - a[id(1, 1)] + a[id(i, 1)])
				//return puts("-1"), void();
				{puts("-1"); return ;}
	for (int i = 1; i <= n; i ++) vec.eb(a[1] - a[(i - 1) * m + 1]);
	for (int i = 1; i <= m; i ++) vec.eb(a[i]);
	sort(vec.begin(), vec.end());
	ll x = vec[(n + m) / 2];//取中位数
	for (auto p : vec) ans += abs(x - p);
	printf("%lld\n", ans); 
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> T;
	while (T --) solve();
	return 0;
}

（额……）

原文地址：http://www.cnblogs.com/YHxo/p/16800260.html