python - 给定 k 个标记的最大项目

Question

数组中有 N 个元素。我可以选择第一项最多 N 次，第二项最多选择 N-1 次，依此类推。

我有 K 个 token 要使用并且需要使用它们以便我可以拥有最大数量的项目。

arr = [3, 4, 8] 其中数组元素表示第 i 项所需的标记

    n = 10 , represents number of tokens I have

Output:

    3

解释:

We have 2 options here:

1. option 1: 1st item 2 times for 6 tokens (3*2) and second item once for 4 tokens (4*1)

2. option 2: 1st item 3 times for 9 tokens (3*3)

so maximum we can have 3 items

代码:

def process(arr,n):
    count = 0
    sum = 0
    
    size = len(arr)+1
    for i in range(0, len(arr), 1):
        size1 = size-1
        size -= 1
        while((sum+arr[i] <= n) and (size1 > 0)):
            size1 = size1 -1
            sum = sum + arr[i]
            count += 1

    return count;

但是它只对少数测试用例有效，它对一些隐藏的测试用例失败了。我不确定我在哪里犯了错误。谁能帮帮我？

Answer 1

对于这样的测试用例，您的贪婪方法将失败:

[8,2,1,1] 10

您的代码将返回 2，但最大值为 6。

我将使用元组的堆，即堆[(cost_of_ride,max_no_rides)]。

请看下面的代码:

from heapq import *

def process(arr,n):
    count = 0
    
    heap = []
    
    for i in range(len(arr)):
        heappush(heap,(arr[i],-(len(arr)-i))) # Constructing min-heap with second index as negative of maximum number of rides 
    
    while(n>0 and heap):
        cost,no_of_rides = heappop(heap)
        no_of_rides = -1 * no_of_rides # Changing maximum no_of_rides from negative to positive
        
        div = n//cost

        # If the amount of money is not sufficient to calculate the last number of rides user could take
        if(div<no_of_rides):
            count += div
            break

        # Else decrement the number of tokens by minimum cost * maximum no_of_rides
        else:
            count += no_of_rides
            n -= no_of_rides*cost
    

    return count;

解决方案的

时间复杂度是:O(len(arr)*lg(len(arr))) 或 O(N*lg(N))。