A. MEX Destruction 题解

题目回顾

给定一个非负整数数组，每次操作可以选择一个子数组，将其替换为该子数组的 $\text{MEX}$（最小未出现非负整数）。 求最少操作次数，将整个数组变为全 $0$。

核心贪心结论（解题关键）

这道题是入门贪心，答案只有三种可能：$\boldsymbol{0、1、2}$，直接判断即可：

1. 数组全为 $0$ → 操作次数：$\boldsymbol{0}$
2. 剔除首尾连续的 $0$ 后，数组中无 $0$ → 操作次数：$\boldsymbol{1}$
3. 剔除首尾连续的 $0$ 后，数组中仍有 $0$ → 操作次数：$\boldsymbol{2}$

结论证明（为什么正确？）

1. 全0数组：无需任何操作，答案为 $0$。
2. 无0数组：直接选择整个数组，其 $\text{MEX}=0$，一步替换为 $0$，答案为 $1$。
3. 含0数组：无法一步将数组变为全0（因为包含0的子数组MEX最小为1），最优策略是两步：
   • 第一步：将中间的非0段替换为一个非0数；
   • 第二步：将整个数组替换为0。

代码逐段解析

主函数

int main()
{
    int t;
    cin >> t;  // 输入测试用例数
    for (int i = 0; i < t; i++)
        solve();  // 逐个处理测试用例
    return 0;
}

核心求解函数 solve()

void solve()
{
    int n; cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];  // 输入数组

    // 步骤1：删除数组**末尾连续的0**
    while (!a.empty() && a.back() == 0)
        a.pop_back();

    // 步骤2：反转数组，删除开头连续的0（等价于删除原数组开头连续的0）
    reverse(a.begin(), a.end());
    while (!a.empty() && a.back() == 0)
        a.pop_back();
    reverse(a.begin(), a.end());

    // 步骤3：处理后数组为空 → 原数组全0，输出0
    if (a.empty())
    {
        cout << 0 << '\n';
        return;
    }

    // 步骤4：判断处理后的数组是否包含0
    bool hasZero = false;
    for (const auto x : a)
        hasZero |= x == 0;
    
    // 含0→2次，无0→1次
    if (hasZero)
        cout << 2 << '\n';
    else
        cout << 1 << '\n';
}

关键操作解释

1. 删除首尾连续0 首尾的0不影响核心判断，只需要保留中间的有效非0段即可。
2. 反转删除 用反转+删除末尾的方式，简洁实现「删除开头连续0」。
3. 含0判断 直接遍历有效数组，快速判断是否存在0。

复杂度分析

• 时间复杂度：$O(\sum n)$，每个元素最多被遍历/删除一次，总长度不超过 $500$，完全满足时间限制。
• 空间复杂度：$O(n)$，存储数组即可。

样例验证

对应题目样例，代码输出完全匹配：

1. 0 1 2 3 → 剔除首尾0后无0 → 输出 $1$
2. 全0数组 → 输出 $0$
3. 1 0 1 0 1 → 剔除首尾0后含0 → 输出 $2$
4. 无0数组 → 输出 $1$

总结

这道题不需要复杂模拟，抓住贪心规律直接判断即可，代码极简且高效，是标准的入门贪心实现题。