题目题解

问题理解

我们有 $n$ 个二进制堆，第 $i$ 个堆初始状态为顶部 $a_i$ 个 $0$、底部 $b_i$ 个 $1$，目标状态为顶部 $c_i$ 个 $0$、底部 $d_i$ 个 $1$。每次操作可以取任意堆的顶部元素，并将其插入到任意堆的任意位置（包括原堆）。求最小操作次数。

关键观察

由于每次只能操作顶部元素，要取出底部的元素，必须先移除其上方的所有元素。因此，每个堆的操作次数取决于需要从该堆顶部移除的元素数量。

下界分析

对于第 $i$ 个堆，考虑两种情况：

1. 如果 $b_i > d_i$（需要移除多余的一）：

   • 这些一在堆的底部，上方有 $a_i$ 个零
   • 要移除一个一，必须先移除它上方的所有零
   • 因此，至少需要移除 $a_i + (b_i - d_i)$ 个元素（所有零加上多余的一）

2. 如果 $a_i > c_i$（需要移除多余的零）：

   • 这些零在堆的顶部，可以直接移除
   • 至少需要移除 $a_i - c_i$ 个零

综上，第 $i$ 个堆至少需要移除的元素数量为：

• 若 $b_i > d_i$：$a_i + b_i - d_i$
• 否则若 $a_i > c_i$：$a_i - c_i$
• 否则：$0$

用公式表示为：

$$\text{need}_i = \begin{cases} a_i + b_i - d_i & \text{if } b_i > d_i \\ a_i - c_i & \text{if } a_i > c_i \\ 0 & \text{otherwise} \end{cases} $$

总操作次数的下界为：

$$\text{ans}_{\min} = \sum_{i=1}^n \text{need}_i$$

可达性证明

这个下界是可以达到的。对于每个需要移除的元素，总存在一个目标堆可以接收它，且放置后不会再被移动：

• 移除一个一：当 $b_i > d_i$ 时，存在某个堆 $j$ 满足 $d_j > b_j$（因为总一数守恒），可以将这个一放置在堆 $j$ 的底部（即所有现有元素之下），这样它永远不会成为顶部元素，无需再次移动。

• 移除一个零：当 $a_i > c_i$ 时，存在某个堆 $j$ 满足 $c_j > a_j$（因为总零数守恒），可以将这个零放置在堆 $j$ 的顶部（即所有现有元素之上），这样它也不会被再次移动。

按照上述策略，每次操作移除一个需要移除的元素并放置到合适的位置，即可用恰好 $\sum \text{need}_i$ 次操作完成变换。

简化公式

观察 $\text{need}_i$ 的表达式，我们可以将其改写为：

$$\text{need}_i = \max(a_i + b_i - d_i, a_i - c_i, 0) $$

但更简洁地，我们可以直接计算：

$$\text{ans} = \sum_{i=1}^n \max(0, a_i - c_i) + \sum_{i=1}^n \max(0, b_i - d_i) + \sum_{i=1}^n [b_i > d_i] \cdot a_i $$

等等，需要仔细验证。

实际上，当 $b_i > d_i$ 时，我们不仅需要移除 $b_i - d_i$ 个一，还需要移除它们上方的所有 $a_i$ 个零。这些零可能本来就需要被移除（如果 $a_i > c_i$），也可能不需要（如果 $a_i \le c_i$）。因此：

• 如果 $a_i > c_i$，移除的零中有 $a_i - c_i$ 个是多余的，其余 $c_i$ 个零是为了拿到一而被迫移除的，但最终这些零需要放回
• 如果 $a_i \le c_i$，则需要移除全部 $a_i$ 个零才能拿到一

因此，更精确的公式是：

$$\text{need}_i = \begin{cases} a_i + b_i - d_i & \text{if } b_i > d_i \\ \max(0, a_i - c_i) & \text{if } b_i \le d_i \end{cases} $$

最终算法

1. 初始化答案 $\text{ans} = 0$
2. 对于每个堆 $i$：
   • 如果 $b_i > d_i$：$\text{ans} \leftarrow \text{ans} + a_i + b_i - d_i$
   • 否则：$\text{ans} \leftarrow \text{ans} + \max(0, a_i - c_i)$
3. 输出 $\text{ans}$

时间复杂度

每个测试用例 $O(n)$，总复杂度 $O(\sum n) \le 2 \times 10^5$，满足要求。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        ll ans = 0;
        
        for (int i = 0; i < n; i++) {
            ll a, b, c, d;
            cin >> a >> b >> c >> d;
            
            if (b > d) {
                // 需要移除所有零加上多余的一
                ans += a + b - d;
            } else {
                // 只需要移除多余的零
                ans += max(0LL, a - c);
            }
        }
        
        cout << ans << "\n";
    }
    
    return 0;
}

样例验证

样例 1：

• 堆1：$b=3 > d=2$ → $\text{ans} += 1 + 3 - 2 = 2$
• 堆2：$b=1 \le d=2$ → $\text{ans} += \max(0, 1-1) = 0$
• 总操作数：$2$ ✓

样例 2：

• 堆1：$b=0 \le d=2$ → $\text{ans} += \max(0, 2-2) = 0$
• 堆2：$b=1 > d=0$ → $\text{ans} += 0 + 1 - 0 = 1$
• 堆3：$b=1 > d=0$ → $\text{ans} += 1 + 1 - 0 = 2$
• 总操作数：$3$ ✓

样例 3：

• 所有堆 $b \le d$ 且 $a \le c$ → $\text{ans} = 0$ ✓

总结

本题的关键在于理解：当需要移除底部的 $1$ 时，必须同时移除其上方所有的 $0$，这些 $0$ 即使不是多余的也要被临时移除。因此，操作次数的下界可以通过上述公式计算，且该下界是可达到的。