字节青训-徒步旅行中的补给问题、贪心猫的鱼干大分配

一、徒步旅行中的补给问题

问题描述

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

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

测试样例

样例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. 问题理解：

   • 小R每天需要消耗1份食物，且每天经过的补给站食物价格不同。
   • 小R最多只能携带K份食物。
   • 目标是找到在N天内完成旅行所需的最小花费。

2. 数据结构选择：

   • 使用动态规划（DP）来解决这个问题。
   • 定义一个二维数组dp[i][l]，表示在第i天结束时，携带l份食物的最小花费。

3. 算法步骤：

   • 初始化：dp[0][0] = 0，表示在第0天结束时，携带0份食物的花费为0。
   • 状态转移：
     • 对于每一天i，我们尝试从之前的某一天j转移过来。
     • 计算在第i天购买食物的花费，并更新dp[i][l]。
   • 返回结果：最终返回dp[n][0]，即在第n天结束时，携带0份食物的最小花费。

具体步骤

1. 初始化DP数组：

   • dp[0][0] = 0，其他dp[0][l]（l > 0）为无穷大。

2. 状态转移方程：

   • 对于每一天i，遍历所有可能的食物携带量l（从0到K）。
   • 对于每一个l，再遍历前一天的所有可能的食物携带量j（从0到K）。
   • 如果l - j + 1在合理范围内（即0 <= l - j + 1 <= K），则更新dp[i][l]。

3. 返回结果：

   • 最终返回dp[n][0]，即在第n天结束时，携带0份食物的最小花费。

最终代码：

def solution(n, k, data):
    dp = [[float('inf')] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    
    for i in range(1, n + 1):
        for l in range(k):
            for j in range(k):
                if l - j + 1 >= 0 and l - j + 1 <= k:
                    dp[i][l] = min(dp[i][l], dp[i - 1][j] + (l - j + 1) * data[i - 1])
    # print(dp)
    return dp[n][0]

if __name__ == "__main__":
    print(solution(5, 2, [1, 2, 3, 3, 2]) == 9)
    print(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9)
    print(solution(4, 1, [3, 2, 4, 1]) == 10)

运行结果：

 二、贪心猫的鱼干大分配

问题描述

在猫星球上，小R负责给一行排队的猫分发鱼干。每只猫有一个等级，等级越高的猫应该得到更多的鱼干。规则如下：

1. 每只猫至少得到一斤鱼干。
2. 如果一只猫的等级高于它相邻的猫，它就应该得到比相邻的猫更多的鱼干。

小R想知道，为了公平地满足所有猫的等级差异，他至少需要准备多少斤鱼干。

测试样例

样例1：

输入：n = 3, cats_levels = [1, 2, 2]
输出：4

样例2：

输入：n = 6, cats_levels = [6, 5, 4, 3, 2, 16]
输出：17

样例3：

输入：n = 20, cats_levels = [1, 2, 2, 3, 3, 20, 1, 2, 3, 3, 2, 1, 5, 6, 6, 5, 5, 7, 7, 4]
输出：35

 解题思路：

问题理解

你需要为每只猫分配鱼干，确保每只猫至少得到一斤鱼干，并且等级高的猫得到的鱼干比相邻的等级低的猫多。

数据结构选择

我们可以使用一个数组 fish_amounts 来记录每只猫的鱼干数量。初始时，每只猫至少得到一斤鱼干，所以 fish_amounts 初始化为 [1] * n。

算法步骤

1. 从左到右遍历：确保每只猫的鱼干数量满足条件。如果当前猫的等级高于前一只猫，那么当前猫的鱼干数量应该比前一只猫多一斤。
2. 从右到左遍历：再次确保每只猫的鱼干数量满足条件。如果当前猫的等级高于后一只猫，那么当前猫的鱼干数量应该比后一只猫多一斤。
3. 计算总鱼干数量：最后，将 fish_amounts 数组中的所有元素相加，得到总的鱼干数量。

关键点

• 从左到右遍历确保每只猫的鱼干数量满足其左侧的猫的等级关系。
• 从右到左遍历确保每只猫的鱼干数量满足其右侧的猫的等级关系。
• 使用 max 函数来确保在两次遍历中，每只猫的鱼干数量不会被减少。

最终代码：

def solution(n, cats_levels):
    # 初始化每只猫的鱼干数量为1
    fish_amounts = [1] * n
    
    # 从左到右遍历，确保每只猫的鱼干数量满足条件
    for i in range(1, n):
        if cats_levels[i] > cats_levels[i - 1]:
            fish_amounts[i] = fish_amounts[i - 1] + 1
    
    # 从右到左遍历，确保每只猫的鱼干数量满足条件
    for i in range(n - 2, -1, -1):
        if cats_levels[i] > cats_levels[i + 1]:
            fish_amounts[i] = max(fish_amounts[i], fish_amounts[i + 1] + 1)
    
    # 返回鱼干总数
    return sum(fish_amounts)

if __name__ == "__main__":
    #  You can add more test cases here
    cats_levels1 = [1, 2, 2]
    cats_levels2 = [6, 5, 4, 3, 2, 16]
    cats_levels3 = [1, 2, 2, 3, 3, 20, 1, 2, 3, 3, 2, 1, 5, 6, 6, 5, 5, 7, 7, 4]
    print(solution(3, cats_levels1) == 4)
    print(solution(6, cats_levels2) == 17)
    print(solution(20, cats_levels3) == 35)

运行结果：