#C6199. Minimum Leveling Operations
Minimum Leveling Operations
Minimum Leveling Operations
You are given a rectangular grid of size \( n \times m \) representing the heights of a plot of land. Your task is to determine the minimum number of leveling operations required to make the entire plot flat. In one leveling operation, you can increase or decrease the height of any cell by 1 unit.
The optimal strategy is to choose a target height \( h^* \) that minimizes the total number of operations. It can be shown that using the median of all cell heights minimizes the sum of absolute differences:
[ \text{operations} = \sum_{i=1}^{n \times m} |h_i - h^*|, ]
where \( h_i \) denotes the height of the \( i \)-th cell. Note that when the number of cells is even, any value between the two middle values minimizes the sum. In this problem, you can choose the \( \lceil \frac{n \times m}{2} \rceil \)-th smallest element as the median.
Your program should read the grid from standard input and output the minimum number of leveling operations required.
inputFormat
The input begins with a line containing two integers \( n \) and \( m \) representing the number of rows and columns of the grid respectively. This is followed by \( n \) lines, each containing \( m \) space-separated integers that represent the heights of the cells.
For example:
3 3 4 2 3 7 6 5 1 2 3
outputFormat
Output a single integer representing the minimum number of leveling operations (i.e., the sum of absolute differences to the chosen median height) required to make the entire grid flat.
For example, for the above input, the output would be:
14## sample
1 1
5
0