徒步旅行中的补给问题

试题分析 #

题目描述：

小R计划一次从地点 A 到地点 B 的徒步旅行，总路程需要 n 天。每天需要消耗 1 份食物，并可以在每天经过的补给站购买食物。补给站的食物价格每天可能不同，小R最多可以同时携带 k 份食物。

目标是：在保证每天都能消耗 1 份食物的前提下，完成徒步旅行的最小花费。

输入：

• n ：旅行总天数。
• k ：背包容量，即最多携带的食物份数。
• text{data[i]} ：第 i 天补给站每份食物的价格。

输出：

• 最小花费。

约束条件：

• 1 < n, k < 1000
• 1 < \text{data[i]} < 10,000

解题思路 #

本题的关键是找到每个窗口内的最小价格，并在满足背包容量限制的情况下尽量从价格最低的补给站购买食物。这是一个典型的滑动窗口最小值问题。

核心问题

1. 每天必须消耗 1 份食物，如果背包中食物不足，需要从价格最低的补给站购买。
2. 背包最多能携带 k 份食物，因此不能过量购买。
3. 如何高效找到当前窗口内（即最近 k 天）的最小价格？

解决方案

使用 单调队列（Deque） 来维护滑动窗口的最小值：

1. 队列维护窗口的最小值：
   • 队列的每个元素存储当前窗口的价格和对应索引。
   • 队列中的值从队尾到队首单调递增，队首元素始终是窗口的最小值。
2. 动态维护窗口：
   • 每次加入新元素时，从队尾移除所有比当前价格大的元素。
   • 每次滑动窗口时，移除队首超出窗口范围的元素。
3. 高效累加结果：
   • 每天累加窗口的最小值，即队首的价格。

复杂度分析 #

1. 时间复杂度：每个元素最多被插入和移除队列一次，因此总时间复杂度为O(n) 。
2. 空间复杂度：双端队列最多存储 k 个元素，因此空间复杂度为O(k)。

代码实现 #

以下是基于 Java 的实现代码：

import java.util.Deque;
import java.util.LinkedList;

public class Main {
    public static int solution(int n, int k, int[] data) {
        // 检查输入有效性
        if (data.length != n || k >= n) {
            throw new IllegalArgumentException("Invalid input");
        }

        // 双端队列存储索引和对应的值，保证队首为窗口的最小值
        Deque<int[]> mins = new LinkedList<>();
        int result = 0;

        for (int j = 0; j < n; j++) {
            // 维护双端队列，确保从队尾到队首值递增
            while (!mins.isEmpty() && mins.peekLast()[1] > data[j]) {
                mins.pollLast();
            }
            mins.addLast(new int[]{j, data[j]});

            // 移除窗口外的元素
            while (!mins.isEmpty() && mins.peekFirst()[0] <= j - k) {
                mins.pollFirst();
            }

            // 当前窗口的最小值累加到结果中
            result += mins.peekFirst()[1];
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试用例
        System.out.println(solution(5, 2, new int[]{1, 2, 3, 3, 2})); // 输出 9
        System.out.println(solution(6, 3, new int[]{4, 1, 5, 2, 1, 3})); // 输出 9
        System.out.println(solution(4, 1, new int[]{3, 2, 4, 1})); // 输出 10
    }
}

代码解析 #

假设 n = 5, k = 2, text{data} = [1, 2, 3, 3, 2] 。我们维护一个窗口大小为 k的滑动窗口，每次只考虑最近 k天的价格。我们用一个队列来存储当前窗口的价格，按从小到大的顺序排列。直接看每天发生了什么。

通过观察每天的变化，我们明确以下核心任务：

1. 维护一个滑动窗口：窗口大小为 k ，表示小R最多能携带的食物天数。
2. 在窗口中找到价格最低的补给站：从窗口中选择最小值，代表当天的最低花费。
3. 动态更新窗口和最小值：
   • 移除过期的值（不在窗口范围内）。
   • 移除比当前值更大的元素，确保队列能快速获取最小值。

关联题目 #