设置时间的最少代价

难度: Medium

常见的微波炉可以设置加热时间，且加热时间满足以下条件：

至少为 1 秒钟。
至多为 99 分 99 秒。

你可以最多输入 4 个数字 来设置加热时间。如果你输入的位数不足 4 位，微波炉会自动加前缀 0 来补足 4 位。微波炉会将设置好的四位数中，前两位当作分钟数，后两位当作秒数。它们所表示的总时间就是加热时间。比方说：

你输入 9 5 4 （三个数字），被自动补足为 0954 ，并表示 9 分 54 秒。
你输入 0 0 0 8 （四个数字），表示 0 分 8 秒。
你输入 8 0 9 0 ，表示 80 分 90 秒。
你输入 8 1 3 0 ，表示 81 分 30 秒。

给你整数 startAt ，moveCost ，pushCost 和 targetSeconds 。一开始，你的手指在数字 startAt 处。将手指移到 任何其他数字 ，需要花费 moveCost 的单位代价。每输入你手指所在位置的数字一次，需要花费 pushCost 的单位代价。

要设置 targetSeconds 秒的加热时间，可能会有多种设置方法。你想要知道这些方法中，总代价最小为多少。

请你能返回设置 targetSeconds 秒钟加热时间需要花费的最少代价。

请记住，虽然微波炉的秒数最多可以设置到 99 秒，但一分钟等于 60 秒。

示例 1：

输入：startAt = 1, moveCost = 2, pushCost = 1, targetSeconds = 600
输出：6
解释：以下为设置加热时间的所有方法。
- 1 0 0 0 ，表示 10 分 0 秒。
  手指一开始就在数字 1 处，输入 1 （代价为 1），移到 0 处（代价为 2），输入 0（代价为 1），输入 0（代价为 1），输入 0（代价为 1）。
  总代价为：1 + 2 + 1 + 1 + 1 = 6 。这是所有方案中的最小代价。
- 0 9 6 0，表示 9 分 60 秒。它也表示 600 秒。
  手指移到 0 处（代价为 2），输入 0 （代价为 1），移到 9 处（代价为 2），输入 9（代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
  总代价为：2 + 1 + 2 + 1 + 2 + 1 + 2 + 1 = 12 。
- 9 6 0，微波炉自动补全为 0960 ，表示 9 分 60 秒。
  手指移到 9 处（代价为 2），输入 9 （代价为 1），移到 6 处（代价为 2），输入 6（代价为 1），移到 0 处（代价为 2），输入 0（代价为 1）。
  总代价为：2 + 1 + 2 + 1 + 2 + 1 = 9 。

示例 2：

输入：startAt = 0, moveCost = 1, pushCost = 2, targetSeconds = 76
输出：6
解释：最优方案为输入两个数字 7 6，表示 76 秒。
手指移到 7 处（代价为 1），输入 7 （代价为 2），移到 6 处（代价为 1），输入 6（代价为 2）。总代价为：1 + 2 + 1 + 2 = 6
其他可行方案为 0076 ，076 ，0116 和 116 ，但是它们的代价都比 6 大。

提示：

0 <= startAt <= 9
1 <= moveCost, pushCost <= 10⁵
1 <= targetSeconds <= 6039

Submission

运行时间: 27 ms

内存: 16.0 MB

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, sec: int) -> int:
        def calc(s: str) -> int:
            cost = pushCost * len(s)
            cur = startAt
            for ch in s:
                if ord(ch) - ord('0') != cur:
                    cost += moveCost
                    cur = ord(ch) - ord('0')
            return cost

        ans = inf
        if 60 <= sec < 6000: ans = calc(f"{sec // 60}{sec % 60 :02}")
        if sec < 100: ans = min(ans, calc(str(sec)))  # 仅输入秒数
        elif sec % 60 < 40: ans = min(ans, calc(f"{sec // 60 - 1}{sec % 60 + 60}"))  # 借一分钟给秒数
        return ans

Explain

本题的目的是找到设置指定秒数的最小代价。由于输入的数字被转换为分钟和秒，因此有多种方式将秒数转换为微波炉的输入。我们需要计算每种方式的代价，并找出其中的最小值。首先，我们定义一个计算输入字符串代价的辅助函数 calc(s)，它计算从开始数字到输入完整个字符串的总代价。然后，根据 targetSeconds，我们考虑以下几种可能的输入方式：1) 直接将秒数转为分钟和秒（如果在可表示范围内），例如 sec = 350，则表示为 '5' '50'。2) 如果 sec < 100，可以直接输入秒数，例如 sec = 76，则表示为 '76'。3) 如果 sec % 60 < 40，可以将一分钟借给秒数，例如 sec = 95，则表示为 '1' '35'（即从 95 秒借 1 分钟变成 35 秒）。最后，我们比较这些可能性的总代价，返回最小值。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, sec: int) -> int:
        def calc(s: str) -> int:
            cost = pushCost * len(s)  # 计算按下按钮的代价
            cur = startAt
            for ch in s:
                if ord(ch) - ord('0') != cur:
                    cost += moveCost  # 如果需要移动，则增加移动代价
                    cur = ord(ch) - ord('0')  # 更新当前位置
            return cost

        ans = float('inf')
        # 尝试直接分钟秒数分开表达
        if 60 <= sec < 6000: ans = calc(f'{sec // 60}{sec % 60 :02}')
        # 尝试只用秒数表达
        if sec < 100: ans = min(ans, calc(str(sec)))
        # 尝试借用一分钟给秒数
        if sec % 60 < 40: ans = min(ans, calc(f'{sec // 60 - 1}{sec % 60 + 60}'))
        return ans

Explore

当秒数为95时，根据题解中的逻辑，我们有几种输入选项。如果直接输入'95'，只涉及到按键代价和可能的移动代价。对于将95秒转换为分钟和秒（1分钟35秒，即'135'），则需要更多的按键和移动操作。因此，如果95秒直接输入为'95'，通常这种情况下的总代价会更低，因为涉及到的按键次数少，且数字连续性更高，移动代价也可能较小。这也解释了为什么在秒数小于100时，直接输入秒数通常是更优的选择。

选择40作为阈值是为了确保在借用一分钟后的秒数（sec % 60 + 60）不超过99，保持在两位数以内。这是因为微波炉的秒数输入通常限制在00到99之间。如果借用分钟使得秒数超过99，那么这种输入方式就变得无效。例如，如果sec % 60是41，借用一分钟后秒数变为101，这超出了可输入的范围。因此，40是一个保证输入有效性的逻辑阈值。

是的，代价计算函数`calc(s)`确实考虑了连续输入同一个数字时移动代价为0的情况。在函数内部，每次输入一个数字前都会检查这个数字是否与当前指针位置相同。如果相同，则不增加移动代价。这通过`if ord(ch) - ord('0') != cur`这个条件判断实现，只有当当前数字与指针位置不同时，才增加移动代价。

当秒数为6000秒时，该数值正好是100分钟，无法直接以秒数形式输入，因为超出了两位数的范围。因此，最合理的输入方式是将其分为分钟和秒，即'10000'。尽管这需要较多的按键和移动操作，但这是唯一可行的方法来设置6000秒，因为其他方法，如直接输入秒或尝试借用分钟，都不适用于这种情况。