SZ#G4M06. 【GESP强化 四级】方格铺地

提交1 通过1
通过率100%
时间限制1000ms
内存限制256MiB

题目描述

刘老师面前有一个 H×WH\times W 的方格区域,第 ii 行第 jj 列的格子上叠放着 AijA_{ij} 个方块。一次操作可以从任意一个仍有方块的格子中取走一个方块,但不能向格子中增加方块。

他要让所有格子上的方块数量完全相同,并希望取走的方块总数尽可能少。需要求出达到目标的最少操作次数。

输入格式

第一行输入两个整数 H,WH,W

接下来 HH 行,每行输入 WW 个整数 AijA_{ij}

输出格式

输出使所有格子方块数相同所需的最少操作次数。

2 3
2 2 3
3 2 2
2
3 3
99 99 99
99 0 99
99 99 99
792
3 2
4 4
4 4
4 4
0

样例解释

  • 样例 1 中,最终都变成全局最小高度,所有差值之和就是操作数。
  • 样例 2 的各格高度已经相同,因此不需要取走方块。
  • 样例 3 中不能把低格补高,只能把所有格降到最低高度。

数据范围与约定

  • 1H,W1001 \le H,W \le 100
  • 0Aij1000 \le A_{ij} \le 100