#C240729A. 周黑鸭(a)

网址（Website）

题目详情 - 周黑鸭(a) - Super

题解 - 周黑鸭(a) - Super

题解（Solution）

$\qquad$设当 $A_{i,j}$ 变为 $B_{i,j}$ 时每一行要加上 $hen[i]$ ，每一列要加上 $shu[j]$ ，则最终的答案就是最小化的 $\sum_{i=1}^n\lvert{hen[i]}\rvert\ +\ \sum_{j=1}^m\lvert{shu[j]}\rvert$，可以推理得确定了$hen[1]$ 之后，其他所有的 $hen[i]$ 与 $shu[j]$ 都可以用 $hen[1]$ 来表示。

$\qquad$（可以自行列一些样例，并且求出答案的表达式）

$\qquad$我们最后要求的的答案就是诸如 $\sum_{k=1}^{n+m}\lvert{hen[1]-a[k]}\rvert$ 的形式，由数学知识，当且仅当 $hen[1]$ 在数组 $a[]$ 的中位数或中位数之间的时候答案有最小值。

$\qquad$（不懂的可以参考小学求$\sum_{i=1}^n \lvert{x-a_i}\rvert$ 最小值的方法）

代码（Code）

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define int long long
#define fi first
#define se second
#define lls (l+r)/3 
inline int input(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2012345;
bool ST;

int n,m,ans;
struct node{
	int v[N];
	int *operator[](int x){return v+x*m;}
}a,b,c;

vector<int> vec;
inline int Solve(){
	vec.clear();
	
	cin>>n>>m;
	For(i,1,n) For(j,1,m) cin>>a[i][j];
	For(i,1,n) For(j,1,m) cin>>b[i][j];
	For(i,1,n) For(j,1,m) c[i][j] = b[i][j]-a[i][j];
	For(i,2,n) For(j,2,m) if(c[i][j]-c[i][j-1]!=c[i-1][j]-c[i-1][j-1]) return -1;
	For(j,1,m) vec.emplace_back(-c[1][j]);
	For(i,1,n) vec.emplace_back(c[i][1]-c[1][1]);
	sort(vec.begin(),vec.end());
	int x = vec[(n+m)/2], res = 0;
	for(auto y:vec) res+=abs(x-y);
	return res;
}

bool ED;
//多测清空 
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int Tim = clock(), T = input();
	while(T--){cout<<Solve()<<'\n';}
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}