列表

详情

2162. 设置时间的最少代价

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

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

给你整数 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 大。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minCostSetTime(int startAt, int moveCost, int pushCost, int targetSeconds) { } };

python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-09-04 17:44:45 

# 模拟
class Solution:
    def minCostSetTime(self, startAt: int, moveCost: int, pushCost: int, targetSeconds: int) -> int:
        # 给定输入的最小花费
        def cost(m: int, s: int) -> int:
            if not (0 <= m <= 99 and 0 <= s <= 99):
                # 输入不合法
                return float("INF")
            digits = [m // 10, m % 10, s // 10, s % 10]
            # 寻找起始位
            start = 0
            while start < 4 and digits[start] == 0:
                start += 1
            
            res = 0   # 最小花费
            prev = startAt
            for d in digits[start:]:
                if d != prev:
                    # 此时需要先移动再输入
                    prev = d
                    res += moveCost
                res += pushCost
            return res
        
        mm, ss = targetSeconds // 60, targetSeconds % 60
        return min(cost(mm, ss), cost(mm - 1, ss + 60))   # 两种可能方案的较小值

golang 解法, 执行用时: 0 ms, 内存消耗: 1.9 MB, 提交时间: 2023-09-04 17:43:49 

func minCostSetTime(startAt, moveCost, pushCost, sec int) int {
	ans := math.MaxInt32
	calc := func(s string) {
		cost := pushCost * len(s)
		cur := startAt
		for _, ch := range s {
			if int(ch&15) != cur {
				cost += moveCost
				cur = int(ch & 15)
			}
		}
		if cost < ans { ans = cost }
	} 
	if sec >= 60 && sec < 6000 {
		calc(fmt.Sprintf("%d%02d", sec/60, sec%60))
	}
	if sec < 100 {
		calc(strconv.Itoa(sec)) // 仅输入秒数
	} else if sec%60 < 40 {
		calc(fmt.Sprintf("%d%d", sec/60-1, sec%60+60)) // 借一分钟给秒数
	}
	return ans
}

python3 解法, 执行用时: 52 ms, 内存消耗: 16.1 MB, 提交时间: 2023-09-04 17:43:32 

# 分类讨论
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

上一题

© 2024 leetcode.cn