简单讲解
|b0 - x| + |b1 - x| + |b2 - x| + |b3 - x| 要达到最小 x 一定是介于 b1 和 b2 之间的数字(b0b1b2b3有序)
所以上述可去掉绝对值: x - b0 + x - b1 + b2 - x + b3 - x = b3 + b2 - b1 - b0
所以每4个数贡献 b3 + b2 - b1 - b0
这里特判奇偶数,如果奇数行,则中间的一行单独处理;同理如果是奇数列,中间一列单独处理
C++代码
int n, m;
int a[maxn][maxn];
void solve(){
read(n, m);
rep(i, 1, n) rep(j, 1, m) read(a[i][j]);
int res = 0;
rep(i, 1, n/2) rep(j, 1, m/2){
int b[4] = {a[i][j], a[i][m+1-j], a[n+1-i][j], a[n+1-i][m+1-j]};
sort(b, b+4);
res += (b[3]+b[2]-b[1]-b[0]);
}
if(n % 2 == 1)
rep(j, 1, m/2){
int b[2] = {a[n/2+1][j], a[n/2+1][m+1-j]};
sort(b,b+2);
res += b[1] - b[0];
}
if(m % 2 == 1)
rep(i, 1, n/2){
int b[2] = {a[i][m/2+1], a[n+1-i][m/2+1]};
sort(b,b+2);
res += b[1] - b[0];
}
cout << res << endl;
}
简洁版
看了看其他大佬的代码,对自己上面写的代码进行简化,可以将特判放入主循环里面
int n, m;
int a[maxn][maxn];
void solve(){
read(n, m);
rep(i, 1, n) rep(j, 1, m) read(a[i][j]);
int res = 0;
rep(i, 1, (n+1)/2) rep(j, 1, (m+1)/2){
int b[4] = {a[i][j], a[i][m+1-j], a[n+1-i][j], a[n+1-i][m+1-j]};
sort(b, b+4);
int temp = (b[3] + b[2] - b[1] - b[0]);
if(i == n+1-i || j == m+1-j){
temp /= 2;
}
res += temp;
}
cout << res << endl;
}