题目描述(CF1422B)
如果一个矩阵能够满足所有的行和列都是回文序列,则称这个矩阵为一个完美矩阵。
一个整数序列 a1,a2,…,ak,如果满足对于任何整数 i(1≤i≤k),等式 ai=ak−i+1 均成立,则这个序列是一个回文序列。
给定一个 n×m 的矩阵 a,每次操作可以将矩阵中的某个元素加一或减一,请问最少经过多少次操作后,可以将矩阵 a 变为一个完美矩阵?
样例
输入样例
2 //接下来有两个矩阵;
4 2 //第一个矩阵的 n, m;
4 2
2 4
4 2
2 4
3 4 //第二个矩阵的 n, m;
1 2 3 4
5 6 7 8
9 10 11 18
输出样例
8
42
数据范围
1≤T≤10 ,
1≤n,m≤100,
0≤aij≤10^9
解题思路
对每次查询 $O(m*n)$
- 由题意分析出:对每个矩阵,保证对每个点,它关于横中心轴和竖中心轴和中心点对称的三个点和它一样,即可保证是一个完美矩阵;
- 由于这样做会重复计算4次,所以最终结果要除以4;
- 跟y总的代码相比,不用处理边界情况,代价就是时间是y总的4倍;
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int mat[101][101], q[4]; //mat[][]用来存储矩阵,q[]是用来把4个点排序的数组;
int main()
{
ios::sync_with_stdio(false);
int t, n, m;
ll sum;
cin>>t;
while(t--){
cin>>n>>m;
sum = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin>>mat[i][j];
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j){ //对每个点,找到它对称的其他三个点;
q[0] = mat[i][j];
q[1] = mat[n-1-i][j];
q[2] = mat[i][m-1-j];
q[3] = mat[n-i-1][m-1-j];
sort(q, q + 4); //对这四个点进行排序;
for(int k = 0; k < 4; ++k)
sum += abs(q[k] - q[1]); //可以是q[1]也可以是q[2];
}
cout<<sum/4<<endl; //记得除4;
}
}