徒步旅行中的补给问题
徒步旅行中的补给问题
问题描述小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
思想：贪心，尽量拿价格小的。
我的想法是：
遍历到后面时，前面的价格应该也要算进来，也就是说走到这个站点，购买的食物应该是从该站点开始往前k个站点最小价格的那一个，因为最多只能携带k份食物，所以遍历到该站点时，那前面的第k+1个站点就需要从所选价格表中删除。
每次插入时都要快速的选取最小值，这就很容易想到一个数据结构——小顶堆（最小堆）。这里使用堆有个问题，就是删除的结点不一定是堆顶，因为不知道前面第k+1个站点价格大小，所以删除结点只能对列表删除结点，然后构建堆，时间复杂度O(n^2*log(n))，不如用一个min_value来记录最小值，复杂度为O(n^2)
def solution(n, k, data):
min_money = 0
ready = []
min_value = 0
for i in data:
ready.append(i)
if len(ready) > k:
ready.pop(0)
min_value = min(ready)
min_money += min_value
return min_money
相关知识
花卉营养缺乏与补给
一种花卉栽培用营养液定时补给装置的制作方法
一种樱桃种植营养液补给装置的制作方法
植物通过什么获得营养 植物通过什么获得营养补给
花卉园林苗木营养缺乏与补给 – 根盆网
肥料应用中存在的问题及建议
如何找到生活中的玫瑰花，让爱情更真实？
5个常见的养花问题，终于找到答案了！
探析雨水花园在住区中的应用
造林绿化存在的问题及对策
网址: 徒步旅行中的补给问题 https://m.huajiangbk.com/newsview860792.html
| 上一篇: 春季多喝五种花茶 助你 |
下一篇: 昆明寻甸花石头山爬山旅游攻略（自 |
