四元组+绝对值和最小值
选择中心对称的四元组分别进行计算。由于行列数目奇偶性的限制,中心会出现二元组,用set优化.
排序后计算 sum(arr[r]-arr[l)) r+l = n-1即可
注:该方法和y总的中位数做法等价
python3 代码
n = int(input())
def calc(mat, s):
points = list(s)
arr = [mat[i][j] for i,j in points]
k = len(arr)
arr.sort()
#print(arr)
ans = 0
#若是偶数 是中位数
#货仓选址 104
l,r = 0, k-1
while l<r:
ans += (arr[r] - arr[l])
l+=1
r-=1
return ans
for i in range(n):
x,y = map(int, input().split())
mat = []
for j in range(x):
mat.append(list(map(int, input().split())))
#print(x,y,mat)
#从四周向中间的四元组相等
#将矩阵分成四个部分,枚举左上角的矩阵即可
#|a-x|+|b-x|+|c-x|+|d-x| 最小 绝对值函数 x = 中位数
res = 0
for i in range((x+1)//2):
for j in range((y+1)//2):
s = [(i,j),(x-1-i,j),(i,y-1-j),(x-1-i, y-1-j)]
tmp = calc(mat, set(s))
#print(tmp)
res += tmp
print(res)