CF_完美矩阵

题目链接 : Acwing. 3565完美矩阵

题目描述

如果一个矩阵能够满足所有的行和列都是回文序列，则称这个矩阵为一个完美矩阵。

一个整数序列$a_1,a_2,…,a_k$，如果满足对于任何整数 i（1≤i≤k），等式 $a_i=a_{k−i+1}$ 均成立，则这个序列是一个回文序列。

给定一个 $n×m$ 的矩阵 a，每次操作可以将矩阵中的某个元素加一或减一，请问最少经过多少次操作后，可以将矩阵 a 变为一个完美矩阵？

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 n 和 m，表示矩阵的大小。

接下来 n 行，每行包含 m 个整数 $a_{ij}$，表示矩阵中的元素。

输出格式

每组数据输出一行，一个答案，表示最少操作次数。

数据范围

1 ≤ T ≤ 10
1 ≤ n,m ≤ 100
0 ≤ $a_{ij}$ ≤ $10^9$

样例

输入样例: 
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

样例解释
第一组数据可以通过 8 步操作得到以下矩阵：
2 2
4 4
4 4
2 2

第二组数据可以通过 42 步操作得到以下矩阵：
5 6 6 5
6 6 6 6
5 6 6 5

算法1

思路分析

由于要求一个这个矩阵的所有行和列都是回文序列, 在$n \times m$ 的矩阵中, 对于$a_{ij}$元素来说其有如下几个元素与它成对称关系:

由于每一个元素都要在所在的行和列找到一个和它相等的回文序列位置上相等的一个元素. 故对于 $a_{ij}$ 来说其在同一行中它的回文位置为 $a_{i, m - j + 1}$, $a_{ij}$在同一列中的它的回文位置为 $a_{n - i + 1, j}$, 同时对于$a_{n - i + 1, j}$ 其同一行(或对于$a_{i, m - j + 1}$的同一列位置来说)的回文位置为 $a_{ n - i + 1, m - j + 1}$ , 故这四个位置的元素要相等. 且这个相等的值X，设这四个位置目前的值分别为 a, b, c, d 则X应该满足的关系为 |X - a| + |X - b| + |X - c| + |X - d| 的值最小, 这个问题就转变为了经典的货仓选址问题(题目链接:Acwing 104. 货仓选址). 故我们的问题就转变了每个 $a_{ij}$ 一般情况下都存在这样一个四元组满足这样一个相等的关系, 我们只要找出这个四元组的，将这四元组的值调整到X, 故调整一次四元组的操作次数就是|X - a| + |X - b| + |X - c| + |X - d|， 我们只要找出一个X， 使得每组的操作次数最小, 那么最后就能求出完美矩阵的最少操作次数. 目前存在的问题就是:

(1) 如何枚举完所有的四元组

• 我们可以发现当我们在$n \times m$ 的矩阵中的左上角找它四元组的其他三个元素时,刚好这三个元素在右上角, 左下角, 右下角这四个区域,故这就相当于我们把左上角的元素的四元组都调整完后，其他三个区域的元素也全部调整完了, 故我们只需要遍历左上角的所有元素均可,找到左上角每一个元素对应的四元组.

(2) 偶数/奇数的行/列的导致某些情况并不存在四元组,,如何特判/统一处理

• 例如对于奇数列的情况, 根据等式 $a_i=a_{k−i+1}$ 找到的回文位置是重合的, 即同一行中的中间元素此时有可能只是二元组或一元组的情况， 针对这种情况, 我们也可以当作四元组处理, 只不过我们在统计计算的时候把这个去重即可.

C++ 代码

时间复杂度 $O(n^2)$

#include<iostream>
#include<algorithm>
#include<vector>
#include<set> 
using namespace std;
using LL = long long;                       // 数据会爆int，故用 long long
using PII = pair<int, int>;                 // pair对组保存行列下标
constexpr int N = 110;                   
int f[N][N]; 

// 用set对输入的坐标数据进行自动的去重处理
auto calc(set<PII> S) -> int
{
    LL res = 0;
    vector<int> q;    
    for(auto &p : S) q.push_back(f[p.first][p.second]);
    sort(q.begin(), q.end()); 
    int n  = q.size(); 
    for(auto v : q)  res += abs(v - q[n / 2]);   // 货仓选址算法,绝对值不等式的应用. 找出每一组四元组最少操作数
    return res; 
}

auto main() -> int
{
    ios::sync_with_stdio(false); 
    int T; cin >> T; 
    while(T--)
    {
        int n, m; cin >> n >> m; 
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= m; ++j) cin >> f[i][j]; 

        LL res = 0;

        // 只遍历矩阵的左上区域
        for(int i = 1; i <= n - i + 1; ++i)    
            for(int j = 1; j <= m - j + 1; ++j) 
                res += calc({{i, j}, {i, m - j + 1}, {n - i + 1, j}, {n - i + 1, m - j + 1}});
        cout << res << endl; 
    }
    return 0;
}