如果一个矩阵能够满足所有的行和列都是回文序列,则称这个矩阵为一个完美矩阵。
一个整数序列 a1,a2,…,aka1,a2,…,ak,如果满足对于任何整数 i(1≤i≤k)i(1≤i≤k),等式 ai=ak−i+1ai=ak−i+1 均成立,则这个序列是一个回文序列。
给定一个 n×mn×m 的矩阵 aa,每次操作可以将矩阵中的某个元素加一或减一,请问最少经过多少次操作后,可以将矩阵 aa 变为一个完美矩阵?
输入格式
第一行包含整数 TT,表示共有 TT 组测试数据。
每组数据第一行包含整数 nn 和 mm,表示矩阵的大小。
接下来 nn 行,每行包含 mm 个整数 aijaij,表示矩阵中的元素。
输出格式
每组数据输出一行,一个答案,表示最少操作次数。
数据范围
1≤T≤101≤T≤10,
1≤n,m≤1001≤n,m≤100,
0≤aij≤1090≤aij≤109
输入样例:
2
4 2
4 2
2 4
4 2
2 4
3 4
1 2 3 4
5 6 7 8
9 10 11 18
输出样例:
8
42
思路
四个数进行排序,找一个数作为操作完之后的数名为c
可以发现如果选的这个c在两个数之间(x1,x2)那么这(x1,x2)的操作数之和是一定小于当这个c在x1,x2之外的
所以要选的这个数c一定是在两个两个数之间所以c的范围是x2<=c<=x3
在这里我们选取x2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=110;
int a[N][N];
int n,m;
LL s,x[4];
int main(){
int T;
cin>>T;
while(T--){
cin>>n>>m;
s=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x[0]=a[i][j];
x[1]=a[i][m-j+1];
x[2]=a[n-i+1][j];
x[3]=a[n-i+1][m-j+1];
sort(x,x+4);
LL xc=abs(x[0]-x[2])+abs(x[1]-x[2])+abs(x[3]-x[2]);
s+=xc;
}
}
cout<<s/4<<endl;
}
}