Hekyのblog

稀土掘金38 补给站最优花费问题

问题描述

小U计划进行一场从地点A到地点B的徒步旅行,旅行总共需要 M 天。为了在旅途中确保安全,小U每天都需要消耗一份食物。在路程中,小U会经过一些补给站,这些补给站分布在不同的天数上,且每个补给站的食物价格各不相同。

小U需要在这些补给站中购买食物,以确保每天都有足够的食物。现在她想知道,如何规划在不同补给站的购买策略,以使她能够花费最少的钱顺利完成这次旅行。

保证第0天一定有一个补给站,并且补给站是按顺序出现的。


测试样例

样例1:

输入:m = 5 ,n = 4 ,p = [[0, 2], [1, 3], [2, 1], [3, 2]]
输出:7

样例2:

输入:m = 6 ,n = 5 ,p = [[0, 1], [1, 5], [2, 2], [3, 4], [5, 1]]
输出:6

样例3:

输入:m = 4 ,n = 3 ,p = [[0, 3], [2, 2], [3, 1]]
输出:9

代码:

int solution(int m, int n, std::vector<std::vector<int>> p) {
    // 在末尾添加一个虚拟站点表示终点,价格设为0(方便处理,但不会实际购买)
    p.push_back({m, 0});
    int totalCost = 0;
    int currentIndex = 0; // 当前站点索引
    while (currentIndex < p.size() - 1) { // 最后一个虚拟站点不作为实际购买点
        int currentDay = p[currentIndex][0];
        int currentPrice = p[currentIndex][1];
        int nextIndex = currentIndex + 1;
        // 找到下一个比当前站价格低的站点或者终点
        while (nextIndex < p.size() && p[nextIndex][1] >= currentPrice) {
          nextIndex++;
        }
        // 如果未找到更便宜的,nextIndex 会指向虚拟终点站
        if (nextIndex == p.size()) {
          nextIndex = p.size() - 1;
        }
        int nextDay = p[nextIndex][0];
        // 计算从当前站到目标站之间需要的天数差
        int daysNeeded = nextDay - currentDay;
        // 在当前站购买足够的食物以覆盖到下一个更便宜的站或终点
        totalCost += daysNeeded * currentPrice;
        // 将当前站点移动到找到的更便宜的站点
        currentIndex = nextIndex;
    }
    return totalCost;
}

tag:
贪心

思路:
用贪心的策略,每次都找一个花费比当前补给站少的点,然后买刚好到那个补给站的食物。然后将当前的位置更新到那个补给站,直到到达终点。

当前页面是本站的「Google AMP」版。查看和发表评论请点击:完整版 »