B. Nice Matrix（模拟+贪心）Codeforces Round #675 (Div. 2)

原题链接： https://codeforces.com/contest/1422/problem/B

测试样例

input
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
output
8
42

Note

In the first test case we can, for example, obtain the following nice matrix in 8 operations:
2 2
4 4
4 4
2 2

In the second test case we can, for example, obtain the following nice matrix in 42 operations:
5 6 6 5
6 6 6 6
5 6 6 5

题意： 给你一个$n\times m$的矩阵，你可以对其中的任意元素进行自增或自减$1$操作。问你至少要经过多少次操作才能使得它变成nice矩阵？nice矩阵的定义为：任一行或任一列都是回文序列。

解题思路： 这道题千万不要想得很复杂，直接模拟操作+贪心即可解决 。为什么呢？我们发现，形成nice矩阵中的每个元素其实都只是和其它两个元素有关系。 对于$a[i][j]$，那么与之关联的就是$a[i][m?j?1]$和$a[n?i?1][j]$（我默认下标从0开始。）。这三个元素要相等，也就是说我们要变化这三个元素。仅此而已。那么该如何变化才能使操作数最小呢？那必然是取三个元素的中间值作为靠拢值，让其它两个元素变化即可。 我们知道了这一步，那么我们就可以直接遍历矩阵了，对每个元素都进行这样的操作（每次进行完操作后都要更改值。），记录所需操作步骤即可。

AC代码

/* *邮箱：unique_powerhouse@qq.com *blog:https://me.csdn.net/hzf0701 *注：文章若有任何问题请私信我或评论区留言，谢谢支持。 * */
#include<bits/stdc++.h> //POJ不支持#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量，a为初始值，n为界限值，递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量， a为初始值，n为界限值，递减。
#define pb push_back
#define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define fi first
#define se second
#define mp make_pairusing namespace std;const int inf = 0x3f3f3f3f;//无穷大
const int maxn = 103;//最大值。
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll>  pll;
typedef pair<int, int> pii;
//*******************************分割线，以上为自定义代码模板***************************************//int t,n,m;
int a[maxn][maxn];
int main(){
    //freopen("in.txt", "r", stdin);//提交的时候要注释掉IOS;while(cin>>t){
    while(t--){
    cin>>n>>m;rep(i,0,n-1){
    rep(j,0,m-1){
    cin>>a[i][j];}}ll cnt=0;//记录操作步骤。//开始模拟操作。rep(i,0,n-1){
    rep(j,0,m-1){
    vector<int> temp;//我们现在所处理的是a[i][j]，与它有关的就是a[i][m-j-1],a[n-i-1][j]。temp.push_back(a[i][j]);temp.push_back(a[i][m-j-1]);temp.push_back(a[n-i-1][j]);sort(temp.begin(),temp.end());//排列取中间值作为靠拢值。a[i][j]=a[i][m-j-1]=a[n-i-1][j]=temp[1];cnt+=(temp[2]-temp[1])+(temp[1]-temp[0]);}}cout<<cnt<<endl;}}return 0;
}