[每日一题] 2739.总行驶距离

博主： Richard
发布时间：2024 年 04 月 25 日
110 次浏览
暂无评论
1348字数
分类： LeetCode

> https://leetcode.cn/problems/total-distance-traveled/description/?envType=daily-question&envId=2024-04-11

### 模拟

这题很简单，主副油箱上限是 100 ，直接模拟就好了：

```c++
class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        int additionalConsume = mainTank / 5, extra = additionalConsume + mainTank % 5;
        while (extra / 5 > 0) {
            additionalConsume +=  extra / 5;
            extra = extra / 5 + extra % 5;
        }
        
        if (additionalConsume > additionalTank)
            additionalConsume = additionalTank;
        
        return (mainTank + additionalConsume) * 10;
    }
};
```

- 时间复杂度：$O(mainTank)$ ，最多循环 $\lceil \frac{mainTank}{4} \rceil$ 次。
- 空间复杂度：$O(1)$ 。

### 数学

可以先架设副油箱的油是无限的，这样的话每跑 50 公里就只需要 4 升油。但这个计算方法在最后一段距离会有问题，比如 8 升油只能跑 90 公里，而不是 100 公里。因为 4 升油的前提是能跑满 50 公里，从而将副油箱的油提前预支过来。所以只需要预留 5 升油保证这个前提就行。因此得到计算公式如下：
$$
extraConsume = \lfloor \frac{mainTank - 5}{4} + 1 \rfloor = \lfloor \frac{mainTank - 1}{4} \rfloor
$$
但是副油箱是有限的，所以只需要取两者中的最小值即可：
$$
extraConsume = min(\lfloor \frac{mainTank - 1}{4}, additionalTank)
$$
加上主油箱的油再乘以速度，就是总共可以行驶的里程了：

```c++
class Solution {
public:
    int distanceTraveled(int mainTank, int additionalTank) {
        return mainTank * 10 + std::min((mainTank - 1) / 4, additionalTank) * 10;
    }
};
```

最后修改：2024 年 05 月 06 日