计算使用的电池总数

Question

假设你有一部手机和几个备用电池。

arr1 =>表示每个电池可以使用的分钟数。

arr2 =>表示每个电池充电所需的分钟数。

• 电池用完后，你可以立即给它充电，然后切换到下一个完全充电的电池。
• 你必须按照数组表示的顺序使用电池。

假设您将使用电话x分钟，返回您将使用的电池数量。

如果无法使用电话，则返回-1。

Example:
arr1 = [12, 3, 5, 18]
arr2 = [8, 1, 4, 9]
x = 16 
output: 3

​

我的守则：

arr1 = [12, 3, 5, 18]
arr2 = [8, 1, 4, 9]
x = 46        # getting correct result when x=16 but not when x=46

def solution(arr1, arr2, x):
    import heapq
    ready,charge=list(range(len(arr1))),[]
    heapq.heapify(ready)
    cur=res=0
    while cur<x:    
        while charge and charge[0][0]<=cur:
            heapq.heappush(ready, heapq.heappop(charge)[1])
            
        if not ready:
            return -1
        
        i=heapq.heappop(ready)    
        res += 1
        cur+=arr1[i]
        heapq.heappush(charge,(cur+arr2[i],i))
    
    return res

solution(arr1, arr2, x)

​

代码提供了一个输出7。

但是，正确的输出是5.

​

Answer 1

似乎您可以通过循环遍历arr1值的总和来实现这一点，直到到达x为止，为每个电池维护一个ready时间列表，以便检查电池当前是否可用：

def solution(arr1, arr2, x):
    numb = len(arr1)
    count = 0
    now = 0
    ready = [0, 0, 0, 0]
    while now < x:
        batt = count % numb
        if ready[batt] > now:
            return -1
        now += arr1[batt]
        ready[batt] = now + arr2[batt]
        count += 1
    return count

solution([12, 3, 5, 18], [8, 1, 4, 9], 16)
# 3
solution([12, 3, 5, 18], [8, 1, 4, 9], 46)
# 5
solution([12, 3, 2], [6, 1, 1], 20)
# -1

Answer 2

这里有一个备用函数，它不需要迭代来找到解决方案。它通过查看电池阵列的总运行时间来计算电池的数量，将x除以所有电池的总运行时，然后查找将覆盖余额(x % total_runtime)的运行时间指数。我给出了几种查找方法，这取决于哪些库(如果有的话)是可用的。

至于是否可以完成呼叫，它会研究每个电池在再次使用之前是否有足够的充电时间(其他电池的运行时间)。如果没有，而且电池必须使用不止一次，呼叫就无法完成。

def solution(arr1, arr2, x):
    # how many batteries?
    numb = len(arr1)
    # make cumulative sum of battery runtimes
    runtimes = [sum(arr1[:i+1]) for i in range(numb)]
    total_runtime = runtimes[numb-1]
    # figure out how many batteries we need
    batts = x // total_runtime * numb
    x = x % total_runtime
    if x > 0:
        batts += bisect.bisect_left(runtimes, x) + 1
        # or
        # batts += np.searchsorted(runtimes, x) + 1
        # or
        # batts += next(idx + 1 for idx, value in enumerate(runtimes) if value >= x)
    # check if any battery we use has a charge time greater than the total runtime of the other batteries
    excess_charge_times = [total_runtime - runtime - arr2[idx] for idx, runtime in enumerate(arr1)]
    # if a battery has to be used more than once and doesn't have enough charge time, fail
    if any(batts > idx + numb and excess_charge_times[idx] < 0 for idx in range(numb)):
        return -1
    return batts