算术练习 详细题解

题目分析

我们有一个初始全为 $0$、长度为 $n$ 的数组 $a$，依次执行 $m$ 次操作： 第 $i$ 次操作选一个下标 $j_i$，执行 $a_{j_i} = x_i - a_{j_i}$。 要求最优选择下标，让最终数组的元素和最大。

核心观察：单元素的操作规律

先看同一个位置被操作 $k$ 次的结果： 设操作序列为 $x_{i_1},x_{i_2},\dots,x_{i_k}$，初始值为 $0$：

• 第1次：$x_{i_1} - 0 = x_{i_1}$
• 第2次：$x_{i_2} - x_{i_1}$
• 第3次：$x_{i_3} - (x_{i_2} - x_{i_1}) = x_{i_3} - x_{i_2} + x_{i_1}$
• 第4次：$x_{i_4} - (x_{i_3} - x_{i_2} + x_{i_1}) = x_{i_4} - x_{i_3} + x_{i_2} - x_{i_1}$

结论： 对一个位置操作 $k$ 次后，最终值为：

$$\begin{cases} \ +x_1 -x_2 +x_3 -x_4 + \dots +x_k & (k为奇数) \\ \ -x_1 +x_2 -x_3 +x_4 - \dots -x_k & (k为偶数) \end{cases} $$

我们把每一个 $x_i$ 对最终和的贡献提取出来： $x_i$ 的系数只能是 $\boldsymbol{+1}$ 或 $\boldsymbol{-1}$！

---

关键推导

1. 总贡献 = 所有 $x_i \times c_i$，其中 $c_i \in \{+1, -1\}$
2. 约束条件：系数为 $-1$ 的 $x_i$ 数量，最多有 $n$ 个
   • 原因：数组只有 $n$ 个位置，每个位置的最后一次操作系数一定是 $+1$，只有非最后一次的操作能取 $-1$，全局最多 $n$ 个 $-1$。

最大化总和的策略

总和公式：

$$\sum_{i=1}^m x_i \times c_i = \sum_{i=1}^m x_i - 2 \times \sum_{(c_i=-1)} x_i $$

要最大化这个值：

• $\sum x_i$ 是固定值
• 等价于 最小化 $\sum_{c_i=-1} x_i$
• 即：选绝对值最小的 $min(n, m)$ 个 $x_i$，把它们的系数设为 $-1$

---

解题步骤

对每个测试 case：

1. 计算所有 $x_i$ 的总和 $total$
2. 对 $x$ 数组按绝对值从小到大排序
3. 取前 $k = min(n, m)$ 个元素，计算它们的和 $sum\_neg$
4. 答案 = $total - 2 \times sum\_neg$

---

复杂度分析

• 时间：$O(M\log M)$，$M$ 为总操作数，排序是核心开销
• 空间：$O(M)$，存储操作数组
• 完全满足题目 $3\times10^5$ 数据限制

---

总结

1. 核心：每个 $x_i$ 只能贡献 $+x_i$ 或 $-x_i$
2. 约束：最多 $n$ 个 $-x_i$
3. 最优：选绝对值最小的 $n$ 个元素取负
4. 公式：$\boldsymbol{ans = \sum x - 2\times\sum(最小绝对值的n个元素)}$