【3分钟吃透】宝石收集最短时间：一道题讲透“贪心策略”的实际应用

【3分钟吃透】宝石收集最短时间：一道题讲透“贪心策略”的实际应用

刷算法题时遇到“图路径最短时间”就慌？这道“七宝石收集”题，其实用小学级数学逻辑+贪心策略就能秒解！今天把官方题解“翻译成人话”，还拆透背后的思维逻辑，以后遇到类似题直接套模板~

一、先看懂题目：别被“图”吓到，其实是个“几何题”

在这里插入图片描述

先把题目里的图简化成人话：

• 7个宝石分布在“中心点（1号）+ 6个外围点”（2-7号）；
• 中心点到外围点的路，走一次花A秒；
• 外围点之间的路，走一次花B秒；
• 规则：从中心点出发，拿到所有7个宝石（到点就拿），求最短时间。

二、核心逻辑：贪心策略——选“更省时间”的走法

在这里插入图片描述

要拿完7个宝石，必须走的路是：从中心点到6个外围点，但外围点之间要不要走？

这里的“贪心”就是：比较“从中心点再走一次A”和“外围点之间走一次B”，哪个更省时间。

拆分路径需求：

1. 首先拿中心点的宝石（1号），不用花时间；
2. 拿6个外围宝石，至少要从中心点出发6次？ → 错！可以拿完一个外围宝石后，走外围路去下一个，不用回中心点。

关键对比：

• 假设拿完外围点X，要去外围点Y：
  • 方案1：回中心点再去Y → 花 A（回中心） + A（去Y） = 2A 秒；
  • 方案2：直接从X走外围路去Y → 花 B 秒；
• 所以，如果B ≤ 2A，就走外围路；如果B > 2A，就回中心点再出发。

总时间计算：

• 基础时间：从中心点到第一个外围点，花 A 秒；
• 剩下5个外围点：每个点的通行时间选“min(2A, B)”；
• 总时间 = A + 5 × min(2A, B)。

三、代码实现：两行核心逻辑，比题解更简洁

看图片里的代码，其实就是把上面的逻辑翻译成C语言：

#include <stdio.h>
int main() {
    int A, B;
    scanf("%d%d", &A, &B);
    // 核心：比较2*A和B，选小的那个
    if (2*A <= B) {
        printf("%d", A + 5*2*A); // 等价于 A*11
    } else {
        printf("%d", A + 5*B);
    }
    return 0;
}

测试用例验证：

比如输入A=2，B=2（对应示例）：

• 2*A=4 > B=2，所以总时间=2 + 5×2=12 → 和示例输出一致！

四、深度拓展：这题背后的“贪心策略”通用场景

这题的本质是**“两点间多路径选择，选成本最低的”**，类似场景：

• 外卖员送单：回站点取餐 vs 直接从当前订单点去下一个；
• 物流运输：回仓库补货 vs 从附近网点调货。

通用解题步骤：

1. 找出“基础成本”（比如这里的“第一次出发的A”）；
2. 找出“可选路径的成本”（比如这里的“2A”和“B”）；
3. 用“基础成本 + 数量×最小可选成本”得到结果。

五、常见误区：别想复杂，这题不用“图算法”

很多人看到“图”就想DFS/BFS，但这题的图结构是固定的（六边形+中心），且路径成本只有两种，贪心策略比图算法更高效——这也是算法题的常见技巧：先看结构是否固定，再选最简解法。

写在最后：算法题的“捷径”是“看透本质”

这道题看起来是“图路径问题”，实际是“贪心策略的数学计算”。以后遇到类似“固定结构+有限成本选项”的题，先别着急写复杂代码，先拆“基础成本”和“可选成本”，往往能秒解！

你遇到过哪些“看起来复杂，实际很简单”的算法题？评论区分享，我帮你拆透逻辑~