徒步旅行中补给问题

小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\

这个题看起来简单，实际挺复杂的。直接看思路。 这样我们可以从未来向过去考虑，当我们步行到某一天时，我们可以选择在之前购买食物，而不是在当前天购买。这样，我们可以通过维护一个单调递增的双端队列来记录当前窗口内的最小价格，从而在每次购买食物时选择最便宜的选项。通过滑动窗口的方式，逐步计算出每天的最小花费，最终得到总的最小花费。
这时候就要用高育良的那句话了:看未来远不如看过去，要来的清楚。
给出解题过程：

1. 初始化：创建一个双端队列 $mins$ 用于存储当前窗口内的最小价格及其对应的天数。初始化结果 $result$ 为0。 遍历每一天：
2. • 维护单调队列：在每次遍历中，首先检查队列 $mins$ 的末尾元素，如果其价格大于当前天的价格，则将其弹出，直到队列为空或队列末尾元素的价格小于等于当前天的价格。然后将当前天的价格和天数加入队列。
   • 滑动窗口：检查队列 $mins$ 的头部元素，如果其对应的天数已经不在当前窗口内（即 $mins[0][0] <= j - k$），则将其弹出。
   • 计算花费：将当前窗口内的最小价格（即队列头部元素的价格）累加到 $result$ 中。
3. 返回结果：遍历结束后，$result$ 即为完成徒步旅行的最小花费。

int solution(int n, int k, std::vector<int> data) {
  //// 初始化一个存储键值对的双端队列 mins，以及结果变量 result
  std::deque<std::pair<int, int>> mins;
  int result = 0;
  // 遍历每一天
  for (int j = 0; j < n; ++j) {
    // 维护单调栈：如果双端队列 mins 的尾部元素的价格高于当前天的价格，将尾部元素弹出
    while (!mins.empty() && mins.back().second > data[j]) {
      mins.pop_back();
    }
    // 将当前天的索引和价格作为键值对添加到双端队列尾部
    mins.push_back(std::make_pair(j, data[j]));
    // 如果双端队列头部元素的索引小于等于 j - k，将头部元素弹出
    while (mins.front().first <= j - k) {
      mins.pop_front();
    }
    result += mins.front().second;
  }

  return result;
}

更新日志

2024/12/13 13:22

查看所有更新日志

• 24fac-prepare interview于 2024/12/13