题意:给你一个 n*m 的矩阵,你可以每次将其中一个数 +1 或 −1 ,求多少次可以使矩阵每一行每一列为回文的。
思路:开始想着算下行和列的平均值做个比较,但写到后面发现保证不了最小次数,然后返回题目中看到题干中有这样一句话if for any integer i (1≤i≤k) the equality ai=ak−i+1 holds.然后根据回文的性质容易得到要想让矩阵行和列为回文,那么矩阵中每个元素只与其它两个元素有关,即对于a[i][j],那么与之关联的就是a[i][m−j+1]和a[n−i+1][j]。取这三个元素的中间值,使其它两个元素改变即可,遍历。
#include <set> #include <map> #include <stdio.h> #include <string.h> #include <cmath> #include <algorithm> #include <iostream> #include <vector> #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define fi first #define se second using namespace std; const int INF = 0x3f3f3f3f;//????? typedef long long ll; typedef long double ld; typedef pair<ll, int> pll; typedef pair<int, int> pii; const int N = 1000000; int a[105][105],b[55],prime[N],st[N];ll sum[N]; int cnt; ll qpow(ll x,ll y,ll mod) { int ans=1; while(y) { if(y&1) ans=ans*x%mod; x=x*x%mod; y>>=1; } return ans%mod; } void ola() { for(int i=2;i<=1000000;i++) { if(st[i]==0) { prime[cnt++]=i; } for(int j=0;j<cnt&&i*prime[j]<=1000000;j++) { st[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main() { IOS; 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 >> a[i][j]; } } ll ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { vector<int> tmp; tmp.push_back(a[i][j]); tmp.push_back(a[i][m-j+1]); tmp.push_back(a[n-i+1][j]); sort(tmp.begin(),tmp.end()); a[i][j]=tmp[1],a[i][m-j+1]=tmp[1],a[n-i+1][j]=tmp[1]; ans+=(tmp[1]-tmp[0])+(tmp[2]-tmp[1]); } } cout << ans << endl; } return 0; }