3749 - keepsideway
描述
Yousef 有 n 列立方体并排摆放。第 i 列包含 a_i 个相同的单位立方体竖直堆叠。初始时重力向下，因此第 i 列恰好包含位于高度 1, 2, \ldots, a_i 的 a_i 个立方体。
突然，重力方向变为向右。每个立方体尽可能向右滑动。立方体不能穿过或重叠其他立方体，且必须保持在原来的高度。最终构型由初始高度唯一确定。
在重力方向改变之前，Yousef 至多可以执行一次操作：选择一个下标 i 并把 a_i 减 1（即从该列移走一个立方体）。他也可以选择不操作。
一个立方体的移动距离定义为 |j-i|，其中 i 是它原来的列下标，j 是重力改变后它所在的列下标。
求 Yousef 能获得的最大总移动距离（即所有剩余立方体的移动距离之和）。
输入
第一行包含一个整数 t（1 \le t \le 10^4）—— 测试用例的数量。接下来是各测试用例的描述。
每个测试用例的第一行包含一个整数 n（1 \le n \le 2\cdot 10^5）—— 数组的长度。
每个测试用例的第二行包含 n 个整数 a_1, a_2, \ldots, a_n（1 \le a_i \le n）—— 数组的元素。
保证所有测试用例的 n 之和不超过 2\cdot 10^5。
输出
对每个测试用例，输出一个整数 —— Yousef 能获得的最大总移动距离。
样例
输入
5 5 1 2 3 2 1 7 5 4 1 1 1 1 3 6 1 2 3 4 5 6 6 4 1 6 3 2 6 7 1 3 2 7 2 3 1
输出
9 37 0 17 29
提示
说明/提示
样例解释：
第一个测试用例：初始总移动距离为 5。若 Yousef 移走下标 5 处的立方体，数组变为 [1,2,3,2,0]。由于第 5 列现在为空，前四列的所有立方体都能比原来滑得更靠右，新的总距离为 9。
第三个测试用例：初始总移动距离为 0。即使移走任意一个立方体，也不会有任何剩余立方体能够移动，因此总距离仍为 0。
来源
复赛测试15
标签