标签: 数组
难度: Easy
标签: 数组
难度: Easy
运行时间: 34 ms
内存: 16.4 MB
class Solution: def getMinimumTime(self, time: List[int], fruits: List[List[int]], limit: int) -> int: ans = 0 for fruit, number in fruits: ans += ceil(number / limit) * time[fruit] return ans
The solution iterates through each batch of fruits specified in the 'fruits' list. For each batch, it calculates the number of times the hero needs to collect fruits of that type to meet the required quantity. This is done by dividing the number of fruits needed ('number') by the maximum number of fruits that can be collected in one go ('limit'), and taking the ceiling of the result to ensure that we account for any remaining fruits that don't make up a full 'limit'. The time taken for each batch is then calculated by multiplying the number of times the hero needs to collect fruits by the time it takes to collect one batch of fruits of that type ('time[fruit]'). The total time taken ('ans') is the sum of the times taken for all batches.
时间复杂度: O(n)
空间复杂度: O(1)
class Solution: def getMinimumTime(self, time: List[int], fruits: List[List[int]], limit: int) -> int: ans = 0 # Initialize the total time taken to 0 for fruit, number in fruits: # Iterate through each batch of fruits ans += ceil(number / limit) * time[fruit] # Calculate and add the time taken for the current batch return ans # Return the total time taken
当`num`(需要采集的果实数量)不是`limit`(每次可以采集的最大数量)的整数倍时,会有一些多余的果实数量无法恰好组成一个完整的`limit`批次。在这种情况下,使用向上取整的方式(ceil函数),保证即使是超出`limit`的部分也被计算为一个完整的采集周期。例如,如果`num`为10,`limit`为3,计算得到的采集次数为`ceil(10/3) = 4`次。这确保了所有果实都被采集完毕,包括最后一次可能不满`limit`的采集。
使用向上取整的方式(ceil函数)是为了确保所有的果实都能被采集完毕。例如,如果一个批次需要采集的果实数除以每次采集的限制数(limit),结果不是一个整数,表示最后一次采集不会达到完整的限制数,但这些果实仍然需要被采集。向上取整能保证即使最后一次采集果实数少于`limit`,也会被算作一次完整的采集过程,从而保障所有果实都被收集。
在算法中,`time`数组是一个整数列表,每个元素代表对应类型果实的采集时间。`fruits`数组是一个二维列表,其中每个子列表包含两个元素:果实的类型(fruit)和需要采集的数量(number)。`fruit`的值作为索引直接用于从`time`数组中获取对应类型果实的采集时间。例如,如果`fruits`中某个元素为`[1, 5]`,则表示类型1的果实需要采集5个,其采集时间由`time[1]`提供。