AcWing 100. 增减序列

题目链接：100. 增减序列 - AcWing题库

求出 $a$ 的差分序列 $b$，其中 $b_1 = a_1$，$b_i = a_i - a_{i - 1} (2 \leq i \leq n)$。

令 $b_{n + 1} = 0$。

题目对序列 $a$ 的操作，相当于每次可以选出 $b_1, b_2, \cdots, b_{n + 1}$ 中的任意两个数，

一个加 $1$，另一个减 $1$。

目标是把 $b_2, b_c, \cdots, b_n$ 变为全零。

最终得到的数列 $a$ 就是由 $n$ 个 $b_1$ 构成的。

从 $b_1, b_2, \cdots, b_{n + 1}$ 中任选两个数的方法可分为四类。

1. 选 $b_i$ 和 $b_j$，其中 $2 \leq i, j \leq n$。 这种操作会改变 $b_2, b_3, \cdots, b_n$ 中两个数的值。 应该保证 $b_i$ 和 $b_j$ 一正一负的前提下，尽量多地采取这种操作，更快地接近目标。
2. 选 $b_1$ 和 $b_j$，其中 $2 \leq j \leq n$。
3. 选 $b_i$ 和 $b_{n + 1}$，其中 $2 \leq i \leq n$。
4. 选 $b_1$ 和 $b_{n + 1}$。 这种情况没有意义，因为它不会改变 $b_2, b_3, \cdots, b_n$ 的值，相当于浪费了一次操作，一定不是最优解。

设 $b_2, b_c, \cdots, b_n$ 中正数总和为 $p$，负数总和的绝对值为 $q$。

首先以正负数配对的方式尽量执行第 $1$ 类操作，可执行 $\min(p, q)$ 次。

剩余 $\lvert p - q \rvert$ 个未配对，每个可以选与 $b_1$ 或 $b_{n + 1}$ 配对，即执行第 $2$ 或第 $3$ 类，共需 $\lvert p - q \rvert$ 次。

综上所属，最少操作次数为 $\min(p, q) + \lvert p - q \rvert = \max(p,q)$ 次。

根据 $\lvert p - q\rvert$ 次第 $2$、第 $3$ 类操作的选择情况，能产生 $\lvert p - q \rvert + 1$ 种不同的 $b_1$ 的值，

即最终得到的序列 $a$ 可能有 $\lvert p - q \rvert + 1$ 种。

完整代码：增减序列.cpp