ClamandFish - 题解

标签与难度

标签: 贪心算法, 思维题, 前瞻性贪心, 后缀和, 字符串处理, 博弈难度: 1600

题目大意喵~

一位可爱的小伙伴要去玩一个钓鱼游戏，游戏总共有 $n$ 个关卡，按顺序从 1 到 $n$ 进行，喵~

每个关卡有四种类型：

类型0: 空空如也，没有鱼也没有蛤蜊。
类型1: 有一个蛤蜊，没有鱼。
类型2: 有一条鱼，没有蛤蜊。
类型3: 有一条鱼，也有一个蛤蜊。

在每个关卡，你 必须且只能 做下面四件事中的一件：

制作鱼饵: 如果当前关卡有蛤蜊，你可以用它制作一个鱼饵。你的鱼饵数量+1。这个鱼饵在之后的关卡才能用哦。
直接钓鱼: 如果当前关卡有鱼，你可以直接把它钓上来，不消耗鱼饵。
用饵钓鱼: 如果你手头有鱼饵，你可以消耗一个鱼饵来钓上一条鱼（即使这个关卡本身没有鱼也行！）。你的鱼饵数量-1。
什么都不做: 路过这个关卡，摸摸鱼（字面意思的摸鱼！）。

现在给你关卡的数量 $n$ 和每个关卡的类型序列，请你计算一下，最多能钓到多少条鱼呢？

解题思路分析

喵哈~！这真是一个有趣的钓鱼游戏呢！要钓到最多的鱼，我们就得精打细算，不能浪费任何一个机会，对吧？这种要求“最优解”的问题，我们通常可以先从贪心的角度来思考，看看每一步是不是都有一个“最好的选择”，呐。

我们来分析一下在每个关卡我们应该做什么决策吧！

1. 无脑的最优选择！

首先，有些决策是显而易见的，喵~

如果一个关卡是 类型2（只有鱼） 或者 类型3（鱼和蛤蜊），那它就有一条现成的、可以免费钓的鱼！
在类型2关卡，我们的选择是“免费钓鱼”或者“用饵钓鱼”。用自己的鱼饵去钓一条本来就免费的鱼，这太亏啦！所以肯定选免费的。
在类型3关卡，我们的选择是“免费钓鱼”或者“制作鱼饵”。一条鱼饵最多也就能在未来换一条鱼，而现在我们能立刻得到一条鱼。一条“今天到手的鱼”肯定比“明天可能钓到的鱼”要香呀！所以，还是直接拿走这条鱼最划算。

结论一: 无论何时遇到类型2或类型3的关卡，我们的最佳策略就是毫不犹豫地选择直接钓鱼！这样鱼的数量+1，鱼饵数量不变。

2. 问题的核心：鱼饵的管理

排除了类型2和3的关卡后，问题就集中在类型0和类型1的关卡上了。这两种关卡都没有免费的鱼，我们的行动都和鱼饵有关。

类型0（空关卡）: 我们唯一能做的有意义的事就是用饵钓鱼。如果我们有鱼饵，就在这里用掉一个换一条鱼，这很划算。
类型1（蛤蜊关卡）: 这是最有趣的决策点！我们有两个选择：
- 选择A: 制作一个鱼饵，为未来做准备。鱼饵数量+1。
- 选择B: 如果我们手头有鱼饵，可以用掉一个来钓一条鱼。鱼饵数量-1，鱼的数量+1。

我们该如何在这两者之间抉择呢？这就要看我们对“鱼饵”的价值判断了。一个鱼饵的价值在于它能在未来变成一条鱼。

一个鱼饵最理想的“消费场所”是类型0的关卡，因为那里除了用鱼饵，没有别的方法能获得鱼。
一个鱼饵第二好的“消费场所”是类型1的关卡。在这里用鱼饵，相当于我们放弃了“制作一个新鱼饵”的机会，来换取“立刻得到一条鱼”。

这启发了我们一个非常聪明的贪心策略：带有前瞻性的贪心！

在每个类型1的关卡，我们做决策前，不妨先“侦察”一下未来的情况。我们最关心的是：未来还有多少个类型0的关卡？因为那是我们鱼饵的“刚需”市场。

让我们定义 future_empty_stages 为从当前关卡的下一关开始，到游戏结束，总共有多少个类型0的关卡。

现在，当我们在一个类型1的关卡时：

假设我们手头有 num_baits 个鱼饵。
如果 num_baits > future_empty_stages: 这说明什么？我们手头的鱼饵比未来最需要它们的地方（类型0关卡）还要多！这些“富余”的鱼饵，如果不在这里用掉，未来可能就没有好地方用了（可能只能在另一个类型1关卡用掉，效果和现在一样）。所以，此时此刻，用掉一个“富余”的鱼饵来换一条鱼，是明智的选择！
如果 num_baits <= future_empty_stages: 这说明我们的鱼饵还不够未来用呢，或者刚刚好。我们应该为未来着想，赶紧利用这个蛤蜊再造一个鱼饵，增加我们的储备！

看，通过比较我们已有的资源（鱼饵）和未来的需求（类型0关卡），我们就能在每个决策点做出当时看来最棒的选择啦！

3. 算法步骤总结

所以，我们的完整算法就是这样哒：

预处理: 从后往前遍历一次关卡序列，计算出一个后缀和数组 future_empty_stages。future_empty_stages[i] 表示从第 i+1 关到最后一关，类型0关卡的总数。
贪心遍历: 从头到尾遍历每一个关卡 i：
- 维护两个变量：fish_caught (已钓到的鱼数) 和 num_baits (当前鱼饵数)。
- 遇到类型2或3: 直接钓鱼！fish_caught++。
- 遇到类型0: 如果有鱼饵 (num_baits > 0)，就用掉一个。fish_caught++, num_baits--。
- 遇到类型1: 进行我们的核心决策！
  - 如果 num_baits > future_empty_stages[i]，说明鱼饵富余，用掉一个！fish_caught++, num_baits--。
  - 否则，说明鱼饵紧缺或刚好，制作一个！num_baits++。
最终结果: 遍历结束后，fish_caught 的值就是我们能钓到的最多鱼数啦，喵~

这个方法是不是很清晰呢？它每一步都考虑了未来的情况，做出了一个局部最优且导向全局最优的决策！

代码实现

下面是我根据这个思路，精心编写的代码实现哦！变量名都很好懂，注释也很详细，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

// 使用一个函数来封装单次测试用例的逻辑，让代码更清晰喵~
void solve() {
    int n;
    std::cin >> n;
    std::string stages;
    std::cin >> stages;

    // 1. 预处理：计算后缀和数组
    // future_empty_stages[i] 表示从 i+1 到 n-1 的关卡中，类型为 '0' 的数量
    std::vector<int> future_empty_stages(n + 1, 0);
    for (int i = n - 2; i >= 0; --i) {
        future_empty_stages[i] = future_empty_stages[i + 1];
        if (stages[i + 1] == '0') {
            future_empty_stages[i]++;
        }
    }

    int fish_caught = 0;
    int num_baits = 0;

    // 2. 贪心遍历：从头到尾处理每个关卡
    for (int i = 0; i < n; ++i) {
        char current_stage_type = stages[i];

        if (current_stage_type == '2' || current_stage_type == '3') {
            // 遇到有免费鱼的关卡，毫不犹豫地拿下！
            fish_caught++;
        } else if (current_stage_type == '0') {
            // 遇到空关卡，是消耗鱼饵的好时机
            if (num_baits > 0) {
                fish_caught++;
                num_baits--;
            }
        } else if (current_stage_type == '1') {
            // 遇到蛤蜊关卡，进行关键决策！
            // 比较当前鱼饵数和未来空关卡数
            if (num_baits > future_empty_stages[i]) {
                // 鱼饵富余，现在用掉一个换鱼更划算
                fish_caught++;
                num_baits--;
            } else {
                // 鱼饵紧缺，为未来做准备，制作一个新鱼饵
                num_baits++;
            }
        }
    }

    std::cout << fish_caught << std::endl;
}

int main() {
    // 加速输入输出，让程序跑得更快，像小猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 。我们首先花 $O(N)$ 的时间预处理了 future_empty_stages 数组。然后，我们又花 $O(N)$ 的时间遍历了一遍所有关卡。总的时间复杂度就是 $O(N) + O(N) = O(N)$ ，非常高效！
空间复杂度: $O(N)$ 。我们用了一个 future_empty_stages 数组来存储后缀和信息，它的大小与关卡数 $N$ 成正比。所以空间复杂度是 $O(N)$ 。

知识点总结

这道题虽然看起来有点绕，但核心思想是非常经典的 贪心算法。

问题分解: 解决复杂问题的第一步，往往是先处理掉最简单、最确定的部分。本题中，我们首先确定了类型2和3关卡的策略，大大简化了问题的决策空间。
前瞻性贪心: 普通的贪心只看眼前利益，而更高级的贪心会“向前看一步”。通过预处理未来的信息（比如本题的后缀和），可以帮助我们在当前做出更优的决策。这是一种在贪心算法中非常有用的技巧。
资源管理: 整个问题可以看作是一个资源（鱼饵）的生产和消耗管理问题。我们的目标是在正确的时机、正确的地点使用资源，以达到效益最大化。
后缀和/前缀和: 这是序列问题中非常常用的预处理技巧，可以让我们在 $O(1)$ 的时间内查询一个区间的某些信息，避免了在主循环中重复计算，从而优化时间复杂度。

希望这篇题解能帮助你理解这道题的精髓，喵~ 如果还有不懂的地方，随时可以再来问我哦！一起努力，变得更强吧！

ClamandFish - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

1. 无脑的最优选择！ ​

2. 问题的核心：鱼饵的管理 ​

3. 算法步骤总结 ​

代码实现 ​

复杂度分析 ​

知识点总结 ​