题解

问题重述

给定一个只包含 $-1, 0, 1$ 的序列，每次操作可以选择一个位置 $i$ ($1 \leq i < n$)，让 $x_{i+1} += x_i$。求使序列变成非递减序列的最少操作次数，或判断无解。

操作的本质

关键观察：操作 x_{i+1} += x_i 实际上是在传播影响：

• 如果 $x_i$ 是正数，操作会让 $x_{i+1}$ 增加
• 如果 $x_i$ 是负数，操作会让 $x_{i+1}$ 减少
• 如果 $x_i$ 是零，操作没有效果

算法思路

核心思想：前缀和与贪心

代码基于第一个元素的值分为三种情况：

情况1：a[1] == 0

if (!a[1]) {
    // 找到第一个非零元素
    if (p < 0) { /* 全零序列 */ }
    else if (a[p] < 0) { /* 无解 */ }
    else { /* 计算操作次数 */ }
}

逻辑：

• 如果全零：不需要操作
• 如果第一个非零是负数：无解（因为0无法传播负值）
• 如果第一个非零是正数：从该位置开始传播正值

情况2：a[1] > 0

cout << N - sum[N] << '\n';

公式解释：最终需要所有元素 ≥ 0，操作次数 = 需要增加的总量。

情况3：a[1] < 0（最复杂）

int ans = sum[N] + N;  // 初始上界
// 遍历寻找最优的分界点

策略：找到一个位置 $i$，使得：

• 前 $i$ 个元素通过操作变成全 -1
• 后 $n-i$ 个元素通过操作变成非递减

关键公式推导

前缀和的作用

sum[i] 表示前 $i$ 个元素的原始和，用于快速计算需要的操作次数。

操作次数计算

对于位置 $i$ 作为分界点：

• 前半部分：sum[i-1] + i - 1
  • sum[i-1]：需要减少的总量
  • i-1：传播需要的操作次数
• 后半部分：(N - i + 1) - (sum[N] - sum[i-1])
  • N-i+1：后半部分长度
  • sum[N]-sum[i-1]：后半部分原始和
  • 差值表示需要增加的总量

代码详解

数据结构

int N, a[MAX_N], sum[MAX_N];
// a[]: 存储原始序列
// sum[]: 前缀和数组，sum[i] = a[1] + a[2] + ... + a[i]

情况1处理

if (!a[1]) {
    int p = -1;
    for (int i = 2; i <= N; i++) {
        if (a[i]) { p = i; break; }  // 找到第一个非零元素
    }
    // 根据第一个非零元素的值判断
}

情况3的优化遍历

for (int i = 2, j; i <= N; i = j) {
    j = i + 1;
    if (a[i] > 0) {
        // 直接计算以i为分界点的代价
        ans = min(ans, sum[i-1] + i-1 + (N-i+1) - (sum[N]-sum[i-1]));
    } else if (!a[i]) {
        // 跳过连续的0，找到下一个非零元素
        for (; j <= N && !a[j]; j++);
        if (j > N || a[j] > 0) {
            // 计算跳过0段后的代价
        }
    }
}

正确性证明

为什么这样贪心有效？

1. 单调性保证：操作只能从左向右传播，所以前面的决策影响后面
2. 最优子结构：每个分界点的选择独立，可以比较所有可能的分界点
3. 边界处理：充分考虑了各种边界情况（全零、首元素特性等）

无解情况

• 首元素为0且第一个非零元素为负
• 其他情况在计算中会自然体现

复杂度分析

• 时间复杂度：$O(n)$
  • 单次遍历计算前缀和：$O(n)$
  • 情况3的遍历：每个元素最多被访问一次，$O(n)$
• 空间复杂度：$O(n)$
  • 存储序列和前綴和数组

样例验证

样例1

输入: -1 1 0 -1 0 1
计算过程：
- a[1] = -1，进入情况3
- 遍历寻找最优分界点，最终找到操作次数为3
输出: 3

样例2

输入: 0 0 -1 -1 1 1
计算过程：
- a[1] = 0，第一个非零元素a[3] = -1 < 0
- 输出: BRAK

学习要点

算法技巧

1. 前缀和优化：快速计算区间和，避免重复计算
2. 分类讨论：根据首元素特性分情况处理，简化问题
3. 贪心选择：遍历所有可能的分界点，选择最优解

问题建模

• 将操作序列问题转化为数学计算问题
• 利用序列特性设计高效算法

边界处理

• 全零序列的特殊处理
• 无解情况的准确判断
• 连续零段的跳过优化

这个解法巧妙利用了问题的特殊性质，通过数学分析和贪心策略达到了线性时间复杂度，是处理大规模数据的高效方案。