一、题目与核心理解
题目描述
Yousef 有 n 列立方体并排摆放。第 i 列竖直堆叠着 a_i 个相同单位立方体。初始重力向下，第 i 列的立方体分别位于高度 1,2,…,a_i。
突然重力转向右方。每个立方体保持自身高度不变，尽可能向右滑动；方块不能重叠、不能互相穿过，最终布局唯一。
在切换重力前，你最多可以执行一次操作：选定下标 i，将 a_i 减 1（移除该列一个立方体）；也可以不操作。
单个立方体移动距离定义为 |j − i|，i 是原始列编号，j 是重力右移后的最终列编号。 求所有剩余立方体移动距离总和的最大可能值。
输入
第一行整数 t (1 ≤ t ≤ 10^4)，代表测试用例数量。 每组测试用例： 第一行整数 n (1 ≤ n ≤ 2・10^5)，代表列数； 第二行 n 个整数 a_1,a_2,…,a_n (1 ≤ a_i ≤ n)。 保证所有测试用例 n 之和 ≤ 2・10^5。
输出
每组输出一个整数：最大总移动距离。
1. 基础设定
- 有
n列立方体，第i列初始有a[i]个单位立方体，竖直堆叠在高度1~a[i]。 - 重力切换为向右：每个立方体保持自身高度不变，尽可能向右滑动，不能重叠、不能穿透其他方块，最终形态唯一。
- 操作权限：最多执行一次操作—— 任选一列，移除 1 个立方体（
a[i] -= 1）；也可以不操作。 - 单块移动距离：
|原列下标i - 最终列下标j|，总距离 = 所有剩余方块移动距离之和。 - 目标：求一次操作 / 不操作下，总移动距离的最大值。
2. 关键现象：右重力下方块的最终排布规律
同一高度层的所有方块会紧密靠右堆叠。 设高度h一共有cnt_h个方块，则高度h的方块最终占据最右侧cnt_h列：
- 原数组所有
a[i] >= h的位置，都贡献 1 个高度 h 方块； - 高度 h 的方块最终列编号：
n - cnt_h, n - cnt_h + 1, ..., n - 1（下标从 0 开始）。
3. 总移动距离数学拆解（核心公式）
设原数组下标0~n-1。
（1）无删除时总距离S
对每一层高度 h：
- 原所有满足
a[i] >= h的下标集合I_h； - 最终位置集合
F_h = {n - cnt_h, ..., n - 1}，cnt_h = |I_h|； 单一层 h 的总移动距离：sum_{x∈F_h} x - sum_{i∈I_h} i全局总距离：S = sum_{h=1}^{maxA} [ sum(F_h) - sum(I_h) ]
拆分求和交换顺序：S = [ sum_{h} sum(F_h) ] - [ sum_{h} sum(I_h) ]
定义两项：
base = sum_{h} sum(F_h)：仅由每层方块数量决定，删除一个方块只会让某一层 h 的 cnt_h 减 1，base 会发生微小变化；raw = sum_{h} sum(I_h)：等价于sum_{i=0}^{n-1} a[i] * i推导：下标 i 会出现在h=1~a[i]共a[i]层，每层累加一次 i，总和就是i*a[i]。
（2）排序数组简化 base 计算
把数组a升序排序得到sorted_a[0], sorted_a[1], ..., sorted_a[n-1]。 对于排序后数组，每层 h 的方块数量等价于>=h的元素个数，高度 h 的最终位置和等价于排序后数组的标准和：base0 = sum_{k=0}^{n-1} sorted_a[k] * kbase0就是不做任何删除时的sum_h sum(F_h)。
无删除原始总距离：ori = base0 - raw
4. 删除一个方块带来的收益（本题核心）
删除位置pos的一个方块，等价于：
- 对高度
h = a[pos]这一层：方块总数cnt_h -= 1； - 原始和
raw减少pos； base会发生变化，变化量为delta_base；- 新总距离 =
(base0 + delta_base) - (raw - pos) = ori + (delta_base + pos)。
我们要最大化总距离，等价于最大化delta_base + pos。
delta_base 怎么求？
原高度h=a[pos]层有cnt个方块，原本占据[n-cnt, n-1]； 删除 1 个后剩cnt-1个，占据[n-(cnt-1), n-1]； 原层和：sum_{x=n-cnt}^{n-1} x新层和：sum_{x=n-cnt+1}^{n-1} x差值delta_base = 新层和 - 原层和 = -(n - cnt)。
设idx为排序数组中第一个>=h的下标，则cnt = n - idx，代入：delta_base = -(n - (n - idx)) = -idx。
因此删除 pos 方块的增量收益：gain(pos) = pos - idx其中idx = lower_bound(sorted_a, h) - sorted_a.begin，h=a[pos]。
最终操作后的总距离最大值：ans = ori + max(0, max(gain(pos) for all pos))
- max (0)：代表可以选择不删除任何方块，收益为 0。
二、代码逐段注释讲解
#include <bits/stdc++.h> using namespace std; // 数组存储原高度，n最大2e5 int a[200005]; int main() { // 快读加速，处理多组大数据 ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; // op：最大增益gain(pos)，初始0（不删除的情况） int op = 0; long long raw = 0; // raw = sum(a[i] * i) vector<int> p, b; // p存候选高度h，b存对应原下标pos cin >> n; // 读取原数组，计算raw for (int i = 0; i < n; i++) { cin >> a[i]; raw += (long long)a[i] * i; } // 筛选有效候选：从右往左遍历，记录严格递减的高度序列 // 原理：只有右侧"高度瓶颈"位置删除，才会产生有效增益；其余位置gain更小 int tm = 1e9; // tm记录当前最小高度，初始极大值 for (int i = n - 1; i >= 0; i--) { if (a[i] == 0) break; // 仅当当前高度小于右侧所有高度时，加入候选 if (a[i] <= tm) { p.push_back(a[i]); b.push_back(i); tm = a[i]; } } // 复制原数组并升序排序，用于计算base0和二分找idx int sorted_a[200005]; memcpy(sorted_a, a, sizeof(int) * n); sort(sorted_a, sorted_a + n); long long base0 = 0; for (int i = 0; i < n; i++) { base0 += (long long)sorted_a[i] * i; } // 遍历所有候选位置，计算gain=pos-idx，更新最大op for (int i = 0; i < p.size(); i++) { int h = p[i]; int pos = b[i]; // 二分查找排序数组中第一个>=h的下标idx int idx = lower_bound(sorted_a, sorted_a + n, h) - sorted_a; op = max(op, pos - idx); } // 最终答案 = 原始总距离 + 最大增益op // 原始总距离 ori = base0 - raw // ans = (base0 - raw) + op cout << base0 - raw + op << '\n'; } return 0; }三、核心重点提炼
1. 两大核心公式
- 无删除原始总距离
ori = sum_{k=0}^{n-1} sorted_a[k] * k - sum_{i=0}^{n-1} a[i] * i - 删除下标 pos、高度 h=a [pos] 的方块带来的增益
gain(pos) = pos - lower_bound(sorted_a, h) - 最终答案
ans = ori + max(0, max(gain(pos)))
2. 优化点（为什么筛选候选 p、b）
若直接遍历全部 n 个位置计算 gain，复杂度O(n log n)，可通过； 但从右往左取严格递减高度作为候选，候选数量远小于 n，二分次数减少，常数更小，适配 2e5 数据范围。
3. 边界样例说明
- 样例 3：
[1,2,3,4,5,6]排序后和原数组完全一致，任意 pos 的pos = idx，gain=0，删除无收益，输出 0； - 样例 1 原数组
[1,2,3,2,1]，原始 ori=5，最优删除位置 gain=4，5+4=9，与样例输出匹配。
4. 数据类型注意
所有求和项会达到2e5 * 2e5 = 4e10，必须使用long long存储raw、base0、最终答案，int 会溢出。
四、算法复杂度分析
每组测试用例：
- 读入 + 计算 raw：
O(n) - 筛选候选：
O(n) - 排序数组：
O(n log n) - 计算 base0：
O(n) - 候选二分：
O(k log n)，k 为候选数量，k≤n 总复杂度O(n log n)，满足sum(n) ≤ 2e5数据限制。
