「ZJOI2020」序列 题解

算法思路分析

这是一个贪心算法问题，需要找到将序列全部变为 $0$ 的最小操作步数。三种操作的区别在于它们影响的元素位置不同，需要巧妙地组合使用。

关键观察

1. 操作类型分析：

   • 操作1：影响区间内所有位置
   • 操作2：只影响奇数位置
   • 操作3：只影响偶数位置

2. 贪心策略：

   • 优先使用操作1（整体操作），因为它效率最高
   • 当操作1无法继续时，使用操作2和操作3来调整奇偶位置

状态维护

代码中维护了几个关键变量：

• b[0], b[1]：分别表示奇数位和偶数位当前可用的操作1次数
• c[0], c[1]：分别表示奇数位和偶数位当前可用的操作2/3次数
• c[2]：表示当前可用的操作1次数
• c[3]：表示当前需要新增的操作次数

核心算法流程

对于每个位置 $a_i$：

1. 计算当前可用的总操作次数 sum = min(c[p] + c[2], b[p])，其中 $p = i \& 1$ 表示奇偶性

2. 情况1：如果现有操作足够覆盖当前值

   if (sum + c[3] <= a) {
       // 调整状态并增加新操作
       ans += c[3] = a - sum - c[3];
   }
   

3. 情况2：如果现有操作部分覆盖当前值

   else if (sum <= a) {
       // 重新分配操作次数
       int d = sum + c[3] - a;
       // 调整各类型操作的数量
   }
   

4. 情况3：如果现有操作超出当前值

   else {
       // 缩减操作次数以适应当前值
       c[p] = min(c[p], b[p] = a);
       c[2] = min(c[2], a);
   }
   

复杂度分析

• 时间复杂度：$O(n)$，只需一次线性扫描
• 空间复杂度：$O(1)$，只使用常数个变量

算法标签

主要分类

• 贪心算法 ⭐⭐⭐⭐⭐

技术子标签

• 奇偶分离 ⭐⭐⭐⭐
• 资源分配 ⭐⭐⭐⭐
• 在线处理 ⭐⭐⭐⭐

问题类型

• 序列处理 ⭐⭐⭐⭐
• 操作优化 ⭐⭐⭐⭐
• 约束满足 ⭐⭐⭐

代码核心逻辑解析

// 关键状态更新
int p = i & 1, sum = min(c[p] + c[2], b[p]);

if (sum + c[3] <= a) {
    // 情况1：需要新增操作
    c[2] += c[3];
    b[0] += c[3]; b[1] += c[3];
    ans += c[3] = a - sum - c[3];
} else if (sum <= a) {
    // 情况2：重新分配操作
    int d = sum + c[3] - a;
    c[2] += a - sum;
    c[!p] += d;  // 调整另一奇偶性的操作
    // 更新边界条件
} else {
    // 情况3：缩减操作
    c[p] = min(c[p], b[p] = a);
    c[2] = min(c[2], a);
}

算法优势

1. 线性复杂度：处理 $n \leq 100000$ 的大数据规模
2. 常数空间：不依赖序列长度
3. 一次扫描：在线处理，无需存储整个序列
4. 最优性：贪心策略保证操作次数最小化

该解法通过巧妙的状态维护和贪心选择，高效地解决了三种操作类型下的最小步数问题，展现了贪心算法在组合优化问题中的强大应用。