很容易想到 a i , m − j + 1 = a n − i + 1 , m − j + 1 = a i , j = a n − i + 1 , j a_{i,m-j+1} = a_{n-i+1,m-j+1} = a_{i,j} = a_{n-i+1,j} ai,m−j+1=an−i+1,m−j+1=ai,j=an−i+1,j 在本题中应该被满足。
这道题主要的难点是我们怎么找到一个数,让这四个数与找到的数的差的绝对值之和最小。
这是一个数学结论,假如我们要找这样一个数 x x x,使得一些数 a , b , c . . . a,b,c... a,b,c... 能够满足 a b s ( a − x ) + a b s ( b − x ) + . . . abs(a-x) + abs(b-x) + ... abs(a−x)+abs(b−x)+...能够取到最小值,这时候 x x x 应该满足是这些数的中位数。
通过中学知识,我们知道对于偶数个数的中位数应该是中间两个数的平均值。
#include<bits/stdc++.h>
using namespace std;
const int N = 110;
#define int long longint g[N][N];
bool vis[N][N];//求中位数的函数
int calc(int a,int b,int c,int d){int arr[4] = {a,b,c,d};sort(arr,arr+4);return (arr[1] + arr[2])/2;
}void solve(){int n,m;cin >> n >> m;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){cin >> g[i][j];vis[i][j] = 0; //记得初始化vis数组}}int res = 0;for(int i = 1;i <= n;i++){for(int j = 1;j <= m;j++){if(!vis[i][j]){//求出中位数int ave = calc(g[i][m-j+1],g[i][j],g[n-i+1][j],g[n-i+1][m-j+1]);//加数过程,这里过程中判断是否被加过,因为题目中有可能出现只需要满足单行或单列的情况res += abs(g[i][m-j+1]-ave);vis[i][m-j+1] = 1;if(!vis[i][j])res += abs(g[i][j]-ave);vis[i][j] = 1;if(!vis[n-i+1][j])res += abs(g[n-i+1][j]-ave);vis[n-i+1][j] = 1;if(!vis[n-i+1][m-j+1])res += abs(g[n-i+1][m-j+1]-ave);vis[n-i+1][m-j+1] = 1;}}}cout << res << endl;
}signed main(){int T;cin >> T;while(T--){solve();}return 0;
}