徒步旅行中的补给问题

问题描述

小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

解题思路

遍历数组 data，对于每个元素，将其添加到 ready 数组中。

如果 ready 数组的长度大于 k，则删除 ready 数组中的第一个元素。

计算当前 ready 数组中的最小值，并将其加到 min_money 中。

返回 min_money。

代码实现

Cangjie

import std.collection.*

func solution(n: Int64, k: Int64, data: Array<Int64>) {
    var min_money = 0
    var ready = ArrayList<Int64>()
    for (i in data) {
        ready.add(i)
        if (ready.size > k) { ready.remove(at: 0) }
        let min_value = ready.iterator().min().getOrThrow()
        min_money += min_value
    }
    min_money
}

main() {
    println(solution(5, 2, [1, 2, 3, 3, 2]) == 9)
    println(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9)
    println(solution(4, 1, [3, 2, 4, 1]) == 10)
}

Rust

fn solution(n: usize, k: usize, data: Vec<i32>) -> i32 {
    let mut min_money = 0;
    let mut ready = Vec::new();
    for &i in &data {
        ready.push(i);
        if ready.len() > k {
            ready.remove(0);
        }
        let min_value = *ready.iter().min().unwrap();
        min_money += min_value;
    }
    min_money
}

fn main() {
   println!("{}", solution(5, 2, vec![1, 2, 3, 3, 2]) == 9);
   println!("{}", solution(6, 3, vec![4, 1, 5, 2, 1, 3]) == 9);
   println!("{}", solution(4, 1, vec![3, 2, 4, 1]) == 10);
}

Python

def solution(n, k, data):
    min_money = 0
    ready = []
    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

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)

JavaScript

function solution(n, k, data) {
    let min_money = 0;
    let ready = [];
    for (let i of data) {
        ready.push(i);
        if (ready.length > k) {
            ready.shift();
        }
        let min_value = Math.min(...ready);
        min_money += min_value;
    }
    return min_money;
}
console.log(solution(5, 2, [1, 2, 3, 3, 2]) == 9);
console.log(solution(6, 3, [4, 1, 5, 2, 1, 3]) == 9);
console.log(solution(4, 1, [3, 2, 4, 1]) == 10);

复杂度分析

时间复杂度：O(n)，其中 n 是数组 data 的长度。遍历数组 data 的时间复杂度为 O(n)，对于每个元素，删除和添加操作的时间复杂度均为 O(k)，因此总的时间复杂度为 O(n+k)。

空间复杂度：O(k)，其中 k 是数组 data 的长度。需要使用一个长度为 k 的数组 ready 来存储当前已经购买的食物价格。

仓颉编程语言