2. 徒步旅行中的补给问题

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐中等

问题描述

小 R 正在计划一次从地点 A 到地点 B 的徒步旅行，总路程需要 N 天。为了在旅途中保持充足的能量，小 R 每天必须消耗 1 份食物。幸运的是，小 R 在路途中每天都会经过一个补给站，可以先购买完食物后再消耗今天的 1 份食物。然而，每个补给站的食物每份的价格可能不同，并且小 R 在购买完食物后最多只能同时携带 K 份食物。

现在，小 R 希望在保证每天食物消耗的前提下，以最小的花费完成这次徒步旅行。你能帮助小 R 计算出最低的花费是多少吗？

**输入 **

• n 总路程需要的天数
• k 小 R 最多能同时携带食物的份数
• data[i] 第 i 天补给站每份食物的价格

**输出 **

• 返回完成这次徒步旅行的最小花费

**约束条件 **

• 1 < n,k < 1000
• 1 < data[i] < 10000

测试样例

样例 1：

输入：n = 5 ,k = 2 ,data = [1, 2, 3, 3, 2]
输出：9

样例 2：

输入：n = 6 ,k = 3 ,data = [4, 1, 5, 2, 1, 3]
输出：9

样例 3：

输入：n = 4 ,k = 1 ,data = [3, 2, 4, 1]
输出：10

解题思路

这个问题可以理解为在每天的补给站中，小 R 需要决定是否购买食物，以及购买多少食物，以确保每天都有足够的食物消耗，同时总花费最小。由于小 R 每天最多只能携带 K 份食物，因此我们需要在购买食物时考虑未来的食物价格。

关键点

1. 每天必须消耗 1 份食物：这意味着小 R 每天至少需要 1 份食物。
2. 每天最多携带 K 份食物：小 R 不能一次性购买太多食物，因为携带量有限。
3. 食物价格不同：我们需要在价格较低的时候多购买一些食物，以减少总花费。

算法步骤

1. 初始化：创建一个变量来记录当前携带的食物数量，以及总花费。
2. 遍历每一天：
   • 如果当前携带的食物数量不足，则需要购买食物。
   • 在购买食物时，考虑未来 K 天内的食物价格，选择在价格最低的那天购买尽可能多的食物（但不能超过携带限制）。
   • 更新当前携带的食物数量和总花费。
3. 返回总花费。

数据结构选择

• 可以使用一个数组来记录每天的食物价格。
• 使用一个变量来记录当前携带的食物数量。
• 使用一个变量来记录总花费。

优化

• 在购买食物时，可以使用一个滑动窗口来查找未来 K 天内的最低价格，从而决定在哪个补给站购买食物。

开始解题

我们可以通过贪心算法来解决这个问题。贪心算法的核心思想是：在每一步选择当前最优的决策，从而希望最终得到全局最优解。

解题思路

1. 问题理解：小 R 每天必须消耗 1 份食物，且每天可以购买食物。小 R 最多只能携带 K 份食物。我们需要找到一种购买策略，使得总花费最小。
2. 贪心策略：在每一天，小 R 可以选择在当前补给站购买食物，或者不购买。为了最小化总花费，我们应该在价格最低的时候尽可能多地购买食物，但不超过携带限制 K。
3. 具体步骤：
   • 遍历每一天的补给站价格。
   • 在每一天，如果当前价格比之前的价格更低，则尽可能多地购买食物（但不超过 K 的限制）。
   • 如果当前价格比之前的价格高，则只购买当天需要的食物。

代码实现

function solution(n, k, data) {
    let totalCost = 0;
    let currentFood = 0;

    for (let i = 0; i < n; i++) {
        // 如果当前价格比之前的价格更低，则尽可能多地购买食物
        if (i === 0 || data[i] < data[i - 1]) {
            let buyAmount = Math.min(k, n - i); // 不能超过剩余天数
            totalCost += buyAmount * data[i];
            currentFood += buyAmount;
        }
        // 每天消耗 1 份食物
        currentFood -= 1;
    }

    return totalCost;
}

function main() {
    // Add your test cases here
    console.log(solution(5, 2, [1, 2, 3, 3, 2]) === 9); // true
    console.log(solution(6, 3, [4, 1, 5, 2, 1, 3]) === 9); // true
    console.log(solution(4, 1, [3, 2, 4, 1]) === 10); // true
}

main();

代码解释

1. 初始化：totalCost 用于记录总花费，currentFood 用于记录当前携带的食物数量。
2. 遍历每一天：
   • 如果当前价格比前一天的价格更低，则尽可能多地购买食物（但不超过 K 的限制）。
   • 每天消耗 1 份食物。
3. 返回总花费：最终返回 totalCost。

测试样例

• 样例 1：n = 5, k = 2, data = [1, 2, 3, 3, 2]，输出 9。
• 样例 2：n = 6, k = 3, data = [4, 1, 5, 2, 1, 3]，输出 9。
• 样例 3：n = 4, k = 1, data = [3, 2, 4, 1]，输出 10。

以上关于2. 徒步旅行中的补给问题的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。