google kickstart block A

Question

Написал код на google kickstart, первую задачу, всё работает, но выдает ошибку runtime error.Как можно сократить код?

n=int(input())
q=0
b=[]
for i in range(n):
    k,m=map(int,input().split())
    a=list(map(int,input().split()))
    a=a[:k]
    while m>=0:
        m-=min(a)
        if m>=0:
            q+=1
            a.remove(min(a))
    b.append(q)
    q=0
for i in range(n):
    print('Case #',i+1,': ',b[i],sep='')

Условие задачи: проблема Есть N домов на продажу. I-й дом стоит Ai долларов, чтобы купить. У вас есть бюджет B долларов, чтобы потратить.

Какое максимальное количество домов вы можете купить?

вход В первой строке входных данных указано количество тестовых случаев, за которыми следуют тесты T. Каждый тестовый пример начинается с одной строки, содержащей два целых числа N и B. Вторая строка содержит N целых чисел. I-е целое число - это Ai, стоимость i-го дома.

Выход Для каждого тестового примера выведите одну строку, содержащую Case #x: y, где x - номер тестового набора (начиная с 1), а y - максимальное количество домов, которое вы можете купить.

*Могу скинуть оригинал на английском

Пример:

Input:
3
4 100
20 90 40 90
4 50
30 30 10 10
3 300
999 999 999

Output:  
Case #1: 2
Case #2: 3
Case #3: 0

Answer 1

1) Ваше решение выдаёт ошибку min() arg is an empty sequence при следующих входных данных:

1
1 300
300

2) В вашем коде много лишних действий. Я оптимизировал его, но всё равно решение не проходит вторую часть тестов из-за TLE (временной лимит исчерпан):

n = int(input())
for i in range(1, n + 1):
    k, m = map(int, input().split())
    a = list(map(int, input().split()))
    cnt = 0
    while m >= 0 and a:
        value = min(a)
        m -= value
        if m >= 0:
            cnt += 1
            a.remove(value)

    print('Case #', i, ': ', cnt, sep='')

Моё решение, прошедшее тесты:

test_cases_num = int(input()) 

for case_num in range(1, test_cases_num + 1): 
    house_num, budget = map(int, input().split())    
    costs = map(int, input().split()) 

    cnt = 0 
    for cost in sorted(costs): 
        budget -= cost
        if budget < 0: 
            break 
        cnt += 1 

    print("Case #{}: {}".format(case_num, cnt))

Моё решение работает быстрее, потому что оно сортирует список один раз, сложность алгоритма сортировки O(N log N).

В вашем решении функция min() вызывается N раз, алгоритм функции min() имеет сложность O(N). В итоге получается сложность O(N^2). Также a.remove(value) вносит свою лепту в снижение производительности, так как она не знает индекс value и каждый раз ищет его в списке, начиная с нулевого элемента.

БЛОГ НА HUSL

google kickstart block A

Ответы (1 шт):