立方体右移重力问题（sort，二分）

一、题目与核心理解题目描述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_{h1}^{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 减 1base 会发生微小变化raw sum_{h} sum(I_h)等价于sum_{i0}^{n-1} a[i] * i推导下标 i 会出现在h1~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_{k0}^{n-1} sorted_a[k] * kbase0就是不做任何删除时的sum_h sum(F_h)。无删除原始总距离ori base0 - raw4. 删除一个方块带来的收益本题核心删除位置pos的一个方块等价于对高度h a[pos]这一层方块总数cnt_h - 1原始和raw减少posbase会发生变化变化量为delta_base新总距离 (base0 delta_base) - (raw - pos) ori (delta_base pos)。我们要最大化总距离等价于最大化delta_base pos。delta_base 怎么求原高度ha[pos]层有cnt个方块原本占据[n-cnt, n-1] 删除 1 个后剩cnt-1个占据[n-(cnt-1), n-1] 原层和sum_{xn-cnt}^{n-1} x新层和sum_{xn-cnt1}^{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.beginha[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) vectorint p, b; // p存候选高度hb存对应原下标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; } // 遍历所有候选位置计算gainpos-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_{k0}^{n-1} sorted_a[k] * k - sum_{i0}^{n-1} a[i] * i删除下标 pos、高度 ha [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 idxgain0删除无收益输出 0样例 1 原数组[1,2,3,2,1]原始 ori5最优删除位置 gain4549与样例输出匹配。4. 数据类型注意所有求和项会达到2e5 * 2e5 4e10必须使用long long存储raw、base0、最终答案int 会溢出。四、算法复杂度分析每组测试用例读入 计算 rawO(n)筛选候选O(n)排序数组O(n log n)计算 base0O(n)候选二分O(k log n)k 为候选数量k≤n 总复杂度O(n log n)满足sum(n) ≤ 2e5数据限制。