徒步中补给问题——贪心算法

贪心算法是一种在每一步选择中都采取在当前状态下最优的选择，以期望通过一系列局部最优的选择达到全局最优的算法。贪心算法通常适用于那些具有最优子结构性质的问题，即问题的最优解可以通过一系列局部最优解的组合得到。

贪心算法的特点

1. 局部最优选择：在每一步选择中，都选择当前状态下的最优解。
2. 无后效性：当前的选择不会影响未来的选择，即当前的选择不会影响未来的状态。
3. 最优子结构：问题的最优解可以通过一系列局部最优解的组合得到。

贪心算法的步骤

1. 问题分解：将问题分解为一系列子问题。
2. 选择策略：在每一步选择中，选择当前状态下的最优解。
3. 验证可行性：验证当前选择是否满足问题的约束条件。
4. 更新状态：根据当前选择更新问题的状态。
5. 重复步骤：重复上述步骤，直到问题解决。

贪心算法在当前问题中的应用

在当前问题中，我们需要在每一天决定购买多少食物，以确保在接下来的几天内都有足够的食物，同时尽量减少花费。我们可以使用贪心算法来实现这一目标。

具体步骤

1. 遍历每一天：从第1天开始，检查当前携带的食物是否足够。
2. 计算需要购买的食物数量：
   • 如果当前食物不足，计算需要购买的食物数量。
   • 购买的食物数量应尽量少，以确保在接下来的几天内都有足够的食物，同时尽量减少花费。
3. 查找下一个更便宜的补给站：
   • 在当前补给站购买食物时，查找未来几天内价格更低的补给站。
   • 购买足够的食物以支撑到下一个更便宜的补给站，或者直到携带上限 K。

问题描述

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

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

测试样例

样例1：

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

样例2：

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

def solution(n, k, data):
    total_cost = 0
    current_food = 0
    
    for day in range(n):
        if current_food < 1:
            # 需要购买食物
            # 查找下一个更便宜的补给站
            next_cheaper_day = day
            while next_cheaper_day < n and data[next_cheaper_day] >= data[day]:
                next_cheaper_day += 1
            
            # 计算需要购买的食物数量
            food_needed = min(k - current_food, next_cheaper_day - day)
            # 计算购买这些食物的花费
            total_cost += food_needed * data[day]
            # 更新当前携带的食物数量
            current_food += food_needed
        
        # 每天消耗1份食物
        current_food -= 1
    
    return total_cost


if __name__ == "__main__":
    # Add your test cases here
    print(solution(5, 2, [1, 2, 3, 3, 2]) )
    print(solution(6, 3, [4, 1, 5, 2, 1, 3]) )
    print(solution(4, 1, [3, 2, 4, 1]) )