原题地址: 传送门
¶分析
对于英文弱鸡的笔者,这道题着实看了很久才看懂题意,同样在一个二维平面内存在着R * C
的格子,且每个格子都会有0≤ Gi,j ≤2*10^6
各盒子,例如:
1 | 0 0 0 |
上述表示R为3,C为3的格子,中间格子的盒子数量为2,其余格子盒子数量为0。
描述到此为止,最终问题是求输入的R*C的格子中,如果要保证每个格子与相邻格子的盒子数量差在1以内,需要在当前规格的基础上,至少增加多少个盒子?
因为最终要保证整个平面内,所有的格子高度差绝对值 <= 1,所以应该从最高的格子开始,让其相邻格子条件,之后除去当前格子,再取剩下格子中最高的格子循环处理,直到当前最高的格子高度为1时结束循环,将新增的盒子数作为答案输出。
分析后的问题转化为将格子从高到低排列,并优先取出最高的格子做处理,并且格子的高度排列是会随着处理过程发生变化,所以使用优先队列处理之!
¶Solve
1 | package main |