伐木机不要石头！！！(easy version) - 题解

标签与难度

标签: 贪心算法, 排序, 双指针, 匹配, 入门难度: 1200

题目大意喵~

你好呀，博士！这次我们要去帮可露希尔砍树啦，喵~ 我们面前有 n 棵树，排成一排，每棵树都有一个坚硬程度 $a_i$ 。同时，我们背包里有 m 把无敌手斧，每把手斧也有一个破坏程度 $b_j$ 。

规则很简单哦：

一把破坏程度为 $b_j$ 的手斧，只有当 $b_j \ge a_i$ 时，才能砍倒坚硬程度为 $a_i$ 的树。
每把手斧只能用一次，砍完一棵树就坏掉啦。
每棵树也只能被砍一次。

我们的任务是，合理地分配手斧去砍树，使得我们能砍倒的树木数量最多！问这个最大数量是多少呢？呐，是不是听起来很有趣呀？

解题思路分析

喵哈哈，这个问题看起来是要我们做一个最优的匹配呢！要把手斧和树木配对，让成功的配对数量最多。一看到“最优”、“最多”这样的字眼，我的直觉就告诉我，这很可能是一个贪心问题哦！

贪心算法的核心思想，就是在每一步都做出当前看起来最好的选择，期望最终能得到全局最好的结果。那么，我们这里的“最好选择”是什么呢？

我们可以换个角度想一想：为了能砍掉尽可能多的树，我们是不是应该“精打细算”，把珍贵的资源用在刀刃上？这里，强大的手斧就是我们的珍贵资源。如果用一把能砍倒最硬树木的超强手斧，去砍一棵最脆弱的小树苗，是不是有点太浪费了呀？这把强力手斧说不定能去挑战一棵其他手斧都搞不定的硬木头呢！

所以，一个非常自然又聪明的贪心策略就出现啦： 为了保留强力手斧去应对坚硬的树木，我们应该用尽可能弱的手斧去砍那些比较脆弱的树。

为了实现这个策略，我们可以先把树木和手斧都“整理”一下。怎么整理最方便呢？当然是排序啦！

我们将所有树木按照它们的坚硬程度 $a_i$ 从小到大排序。
我们也将所有手斧按照它们的破坏程度 $b_j$ 从小到大排序。

这样一来，我们就有了最脆弱的树、第二脆弱的树……以及最弱的手斧、第二弱的手斧……

现在，我们可以开始我们的“配对大作战”了！我们可以用经典的双指针技巧来高效地完成这个过程，喵~

我们设置两个指针：

一个指针 tree_ptr 指向当前正在考虑的树，从最脆弱的树开始（排序后数组的第0个）。
另一个指针 axe_ptr 指向当前可用的手斧，也从最弱的手斧开始（排序后数组的第0个）。

然后我们开始遍历：

情况一： 如果当前 axe_ptr 指向的手斧 b[axe_ptr] 的破坏程度 大于或等于 tree_ptr 指向的树 a[tree_ptr] 的坚硬程度（即 b[axe_ptr] >= a[tree_ptr]）。太棒了，可以砍！喵~ 这正是我们想要的！我们找到了能砍倒当前这棵树的、并且是所有可用斧头中最弱的一个。我们就用它了！于是，成功砍倒一棵树，我们的计数器加一。然后这棵树和这把斧头都“功成身退”了，所以我们把 tree_ptr 和 axe_ptr 都向后移动一位，去考虑下一棵树和下一把手斧。
情况二： 如果当前 axe_ptr 指向的手斧 b[axe_ptr] 的破坏程度小于 tree_ptr 指向的树 a[tree_ptr] 的坚硬程度（即 b[axe_ptr] < a[tree_ptr]）。哎呀，这把手斧太弱了，连当前这棵最脆弱的待选树都砍不动。因为我们已经把树木排好序了，所以这把手斧肯定也砍不动后面那些更硬的树。那么这把可怜的手斧对我们剩下的任务就没有任何帮助了，我们只能放弃它，试试下一把更强壮的手斧。所以，我们只将 axe_ptr 向后移动一位，而 tree_ptr 保持不动，继续为当前这棵树寻找合适的斧头。

我们不断重复这个过程，直到我们的树木指针或者手斧指针超出了数组的范围，就说明我们已经考虑完所有可能性啦。

举个例子吧，博士！假设树的坚硬程度是 a = [20, 5, 15]，手斧的破坏程度是 b = [10, 22, 12]。

排序： a_sorted = [5, 15, 20]b_sorted = [10, 12, 22]
双指针匹配：
- tree_ptr = 0 (树硬度5), axe_ptr = 0 (斧破坏10)。10 >= 5？是的！成功砍掉一棵！count = 1。两个指针都后移：tree_ptr = 1, axe_ptr = 1。
- tree_ptr = 1 (树硬度15), axe_ptr = 1 (斧破坏12)。12 >= 15？不是。斧头太弱了。放弃这把斧头，axe_ptr 后移：tree_ptr = 1, axe_ptr = 2。
- tree_ptr = 1 (树硬度15), axe_ptr = 2 (斧破坏22)。22 >= 15？是的！成功砍掉第二棵！count = 2。两个指针都后移：tree_ptr = 2, axe_ptr = 3。
- 现在 axe_ptr = 3，已经没有手斧了。循环结束。

最终，我们最多可以砍掉 2 棵树。这个方法是不是既简单又高效呢，喵~

代码实现

这是我根据上面的思路，精心为你准备的一份C++代码哦~ 注释写得很详细，希望能帮到你，博士！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 为了加速输入输出，让程序跑得更快一点，喵~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    // 读取树的数量 n 和手斧的数量 m
    std::cin >> n >> m;

    // 使用 vector 来存储树的坚硬程度
    std::vector<int> tree_hardness(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> tree_hardness[i];
    }

    // 使用 vector 来存储手斧的破坏程度
    std::vector<int> axe_damage(m);
    for (int i = 0; i < m; ++i) {
        std::cin >> axe_damage[i];
    }

    // 贪心策略的第一步：排序！
    // 将树木按坚硬程度从小到大排序
    std::sort(tree_hardness.begin(), tree_hardness.end());
    // 将手斧按破坏程度从小到大排序
    std::sort(axe_damage.begin(), axe_damage.end());

    int cut_count = 0; // 用来记录成功砍伐的树木数量
    int tree_ptr = 0;  // 指向当前要砍的树
    int axe_ptr = 0;   // 指向当前可用的手斧

    // 双指针开始工作！只要还有树并且还有手斧，就继续匹配
    while (tree_ptr < n && axe_ptr < m) {
        // 如果当前的手斧足够强大，可以砍倒当前的树
        if (axe_damage[axe_ptr] >= tree_hardness[tree_ptr]) {
            // 耶！成功砍伐！
            cut_count++;
            // 这棵树和这把手斧都用掉了，我们去看下一棵树和下一把手斧
            tree_ptr++;
            axe_ptr++;
        } else {
            // 哎呀，这把手斧太弱了，砍不动这棵树
            // 因为树是排好序的，所以它也砍不动后面的任何一棵树
            // 我们只能放弃这把手斧，试试下一把更强的
            axe_ptr++;
        }
    }

    // 所有能砍的都砍完啦，输出结果
    std::cout << cut_count << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N \log N + M \log M)$ 主要的时间开销在于两个排序操作。对 n 棵树排序需要 $O(N \log N)$ 的时间，对 m 把手斧排序需要 $O(M \log M)$ 的时间。之后的双指针遍历过程，两个指针都只会从头到尾移动一次，所以这部分的时间复杂度是 $O(N + M)$ 。因此，总的时间复杂度由排序决定，为 $O(N \log N + M \log M)$ ，喵~
空间复杂度: $O(N + M)$ 我们主要使用了两个 std::vector 来存储树的坚硬程度和手斧的破坏程度，它们的大小分别是 n 和 m。所以，我们占用的额外空间是 $O(N + M)$ 。

知识点总结

这道题虽然是 easy version，但它包含了一些非常重要和基础的算法思想哦！

贪心算法 (Greedy Algorithm): 这是解决本题的核心。我们通过制定一个局部最优策略（用最弱的可用斧头砍当前最弱的树）来达到全局最优（砍伐总数最多）。识别问题是否能用贪心是解题的关键一步，呐。
排序 (Sorting): 排序是许多贪心算法和其它高效算法的“好朋友”。它能为问题提供一个清晰的结构，让我们的贪心选择变得简单和正确。
双指针 (Two Pointers): 当处理一个或多个有序数组时，双指针是一个非常强大的技巧。它能将通常需要嵌套循环（ $O(N^2)$ ）的问题优化到线性扫描（ $O(N)$ ），大大提高了程序的效率！

希望这篇题解能对博士有所帮助！如果还有什么问题，随时可以来问我哦，喵~

伐木机不要石头！！！(easy version) - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​