Balancing 详细题解

题目分析

核心题意

给定一个相邻元素互不相等的数组 $a_1,a_2,\dots,a_n$，要求用最少的操作次数将数组变成严格递增数组。

每次操作规则： 选择区间 $[l,r]$，将这个区间内的数整体替换，替换后必须保留原区间内相邻元素的大小关系（原 $a_i<a_{i+1}$ 则新数也必须 $a'_i<a'_{i+1}$；原 $a_i>a_{i+1}$ 则新数也必须 $a'_i>a'_{i+1}$）。

求最小操作次数。

---

关键观察（核心突破口）

1. 严格递增数组的本质：所有相邻元素都必须满足 $a_i < a_{i+1}$。
2. 操作的作用：一次操作可以修复一段连续的「下降关系」，但无法改变区间内的大小关系，只能修改数值。
3. 核心定义：我们把数组中所有 $a_i > a_{i+1}$ 的位置称为下降点，记总下降点数量为 $\boldsymbol{ans}$。

---

标程逻辑深度解析

步骤1：统计所有下降点

遍历数组，统计所有满足 $a_i > a_{i+1}$ 的位置：

• 每遇到一个下降点，ans += 1
• 记录第一个下降点的左位置 pos1（第一个 $a_i>a_{i+1}$ 的 $i$）
• 记录最后一个下降点的右位置 pos2（最后一个 $a_i>a_{i+1}$ 的 $i+1$）

步骤2：判断两种情况

标程核心判断公式：

if ((ans & 1) || (pos1 && a[pos2] - a[pos1] < pos2 - pos1))
    答案 = (ans >> 1) + 1
else
    答案 = ans >> 1

翻译为数学语言：

1. 情况1：下降点数量 $\boldsymbol{ans}$ 是奇数 $\rightarrow$ 最小操作次数 $= \lfloor \frac{ans}{2} \rfloor + 1$
2. 情况2：下降点数量 $\boldsymbol{ans}$ 是偶数，但首尾下降区间无法直接拼接成严格递增 （即 $a[pos2] - a[pos1] < pos2 - pos1$） $\rightarrow$ 最小操作次数 $= \lfloor \frac{ans}{2} \rfloor + 1$
3. 情况3：下降点数量 $\boldsymbol{ans}$ 是偶数，且可以直接拼接 $\rightarrow$ 最小操作次数 $= \lfloor \frac{ans}{2} \rfloor$

---

原理推导

1. 下降点的分组规律

一次操作最多可以修复 2 个连续的下降点：

• 下降点是 $a>b>c$ 这种连续下降段
• 一次操作修改 $[1,3]$，可以把它改成严格递增，一次性修复 2 个下降点

因此：

• 偶数个下降点：理论最少操作数 $= \frac{ans}{2}$
• 奇数个下降点：必须多一次操作，最少操作数 $= \frac{ans}{2} + 1$

2. 偶数下降点的特殊判断

即使下降点是偶数，也可能无法用 $\frac{ans}{2}$ 次完成： 需要满足首尾可拼接严格递增：

$$a[pos2] - a[pos1] \ge pos2 - pos1$$

• $pos1$：第一个下降的左位置
• $pos2$：最后一个下降的右位置

如果不满足，说明无法一次合并修复，必须额外加 1 次操作。

---

标程代码逐行解释

// 统计下降点 ans，记录第一个下降左pos1，最后一个下降右pos2
for (ll i = 1;i < n;i += 1) if (a[i] > a[i + 1]){
    ans += 1,pos2 = i + 1;
    if (!pos1) pos1 = i;
}

// 核心判断
// 1. 下降点奇数  OR  2. 偶数但无法拼接 → 答案=ans/2 +1
if ((ans & 1) || (pos1 && a[pos2] - a[pos1] < pos2 - pos1))
    printf("%lld\n",(ans >> 1) + 1);
// 偶数且可拼接 → 答案=ans/2
else
    printf("%lld\n",ans >> 1);

• ans & 1：判断奇数（二进制最后一位为1）
• ans >> 1：等价于整数除法 $\lfloor \frac{ans}{2} \rfloor$
• pos1：第一个下降点左侧位置
• pos2：最后一个下降点右侧位置

---

样例验证（对照输入输出）

样例1

输入：

3
3 2 1

• 下降点：$3>2$、$2>1$ → $ans=2$（偶数）
• 判断：$a[3]-a[1] = 1-3=-2 < 3-1=2$
• 答案：$\frac{2}{2}+1=2$ ✔️

样例2

输入：

3
3 1 2

• 下降点：$3>1$ → $ans=1$（奇数）
• 答案：$\frac{1}{2}+1=1$ ✔️

样例3

输入：

4
-2 -5 5 2

• 下降点：$-2>-5$、$5>2$ → $ans=2$（偶数）
• 答案：$\frac{2}{2}=1$ ✔️

样例4

输入：

7
1 9 1 9 8 1 0

• 下降点：$9>1$、$9>8$、$8>1$、$1>0$ → $ans=4$
• 判断不满足拼接条件 → 答案 $\frac{4}{2}+1=3$ ✔️

---

复杂度分析

• 时间复杂度：$\boldsymbol{O(\sum n)}$ 每个测试用例仅遍历一次数组，总长度不超过 $2 \times 10^5$，完全符合时间限制。
• 空间复杂度：$\boldsymbol{O(n)}$ 存储数组即可，无额外空间开销。

---

总结

1. 核心指标：统计数组中下降点数量 $ans$（$a_i>a_{i+1}$ 的次数）。
2. 判断规则：
   • 下降点为奇数 $\rightarrow$ 答案 $= \frac{ans}{2}+1$
   • 下降点为偶数但无法拼接 $\rightarrow$ 答案 $= \frac{ans}{2}+1$
   • 下降点为偶数且可拼接 $\rightarrow$ 答案 $= \frac{ans}{2}$
3. 拼接条件：$a[pos2]-a[pos1] \ge pos2-pos1$。