题目概述

Bajtazar 在银行的账户流水是一串 +（存入1元）和 -（取出1元）的序列。已知：

• 初始余额：p
• 最终余额：q
• 当前流水序列：长度为 n 的 +/- 字符串

要求修正流水，使得：

1. 按流水操作后，最终余额等于 q
2. 操作过程中余额始终 ≥ 0

可以进行的操作：

• 花费 x 秒：将任意一个操作改为相反操作（+ ↔ -）
• 花费 y 秒：将最后一个操作移到开头

求最少需要多少秒完成修正。

---

问题分析

关键观察

1. 余额约束：操作过程中不能出现负数余额
2. 最终余额：操作后的余额必须等于 q
3. 操作类型：有两种修正方式，需要找到最优组合

数学建模

设原序列中：

• + 的数量为 cnt_plus
• - 的数量为 cnt_minus

那么当前序列的净效果是：cnt_plus - cnt_minus

要达到最终余额 q，需要满足：

p + (cnt_plus - cnt_minus) = q

即：

cnt_plus - cnt_minus = q - p

但当前序列可能不满足这个条件，也可能违反非负余额约束。

---

算法思路

步骤1：计算需要修改的操作次数

设需要将 k 个操作从 - 改为 +（或者相反），使得净效果等于 q-p。

通过计算可得：

k = |(当前净效果 - (q-p)) / 2|

每个修改花费 x 秒，这部分基础代价为 |k| * x。

步骤2：处理余额非负约束

即使净效果正确，序列仍可能在某处使余额变为负数。

通过循环移动序列（将末尾操作移到开头），可以改变余额的变化过程，避免负数余额。

步骤3：滑动窗口求最小代价

将原序列复制一份接在后面，形成 2n 的序列。

使用单调队列维护每个位置作为起点时，序列运行过程中的最小余额。

对于每个可能的循环移动位置，计算：

• 如果需要提升最低余额，额外修改一些操作
• 移动操作的花费

取所有情况的最小值。

---

算法详解

核心变量

• k：需要修改的操作数量
• a[i]：操作序列（+1 表示存入，-1 表示取出）
• val[i]：相对余额变化
• tag：累计变化量
• q：单调队列，维护最小值

关键函数 ins(int idx)

这个函数维护滑动窗口的最小值：

ll ins(int idx) {
    val[idx] = -tag;           // 记录当前相对值
    // 维护队列范围
    while (!q.empty() && q.front() >= idx + n)
        q.pop_front();
    
    tag += a[idx];             // 更新累计变化
    
    // 维护单调性
    while (!q.empty() && val[q.back()] > val[idx])
        q.pop_back();
        
    q.push_back(idx);
    return val[q.front()] + tag;  // 返回实际最小值
}

主算法流程

1. 计算 k：

   k = (cnt[1] - cnt[0] - tgt + ori) / 2;
   

2. 复制序列：将原序列复制一份，便于处理循环移动

   for (int i = n + 1; i <= 2 * n; ++i)
       a[i] = a[i - n];
   

3. 滑动窗口扫描：

   • 从后往前处理每个位置作为起点的情况
   • 计算该起点对应的最小余额
   • 如果最小余额不足，计算需要额外修改的操作数

4. 计算总代价：

   ans = min(ans, ...) + abs(k) * x;
   

---

样例解析

样例输入

9 2 3 2 1
---++++++

分析：

• 初始余额 p = 2，最终余额 q = 3
• 当前序列：---++++++（3个-，6个+）
• 净效果：6 - 3 = 3，最终余额应为 2 + 3 = 5，但要求是 3

计算 k：

k = (6 - 3 - 3 + 2) / 2 = (2) / 2 = 1

需要修改1个操作。

通过算法找到最优方案：移动并修改，总代价为3。

---

复杂度分析

• 时间复杂度：$O(n)$
  • 序列复制：$O(n)$
  • 单调队列扫描：每个元素入队出队一次，$O(n)$
• 空间复杂度：$O(n)$
  • 存储扩展序列和辅助数组

---

算法亮点

1. 问题转化：将余额约束转化为序列最小值问题
2. 循环移动：通过复制序列处理所有可能的移动方案
3. 单调队列：高效维护滑动窗口最小值
4. 代价计算：综合考虑修改和移动操作的代价

---

总结

这道题的核心在于：

1. 理解约束条件：最终余额正确 + 过程中余额非负
2. 操作分析：修改操作改变净效果，移动操作改变余额变化过程
3. 高效算法：使用单调队列在线性时间内找到最优解
4. 代价优化：平衡修改和移动操作的代价

这种"序列约束 + 操作优化"的问题在编程竞赛中很常见，单调队列是解决滑动窗口极值问题的有力工具。