Link do problemu: https://codingCompetitions.Withgoogle.com/KickStart/round/000000000019FC7 / 00000000001D3F56.

problem Należy na sprzedaż. I-TH House kosztuje dolarów za zakup. Masz budżet Dolarów B, aby wydać. Jaka jest maksymalna liczba domów, które możesz kupić?

Wejście Pierwsza linia wejścia zawiera liczbę przypadków testowych, następują przypadki T. T. Każda sprawa testowa rozpoczyna się od pojedynczej linii zawierającej dwa liczby całkowite N i B. Druga linia zawiera N Ciężci całkowite. I-th Integer to AI, koszt domu I-TH.

wyjście Dla każdej sprawy testowej Wyjście jeden wiersz zawierający futerał #x: y, gdzie X jest numer sprawy testowej (począwszy od 1), a Y jest maksymalną liczbą domów, które można kupić.

limity

Limit czasu: 15 sekund na zestaw testowy.

Limit pamięci: 1 GB.

  • 1 ≤ t ≤ 100.
  • 1 ≤ b ≤ 105.
  • 1 ≤ AI ≤ 1000, dla wszystkich i.

zestaw testowy 1

1 ≤ N ≤ 100.

zestaw testowy 2

1 ≤ N ≤ 105.

Przykładowe wejście

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

Wyjście próbki

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

W przykładowym przypadku # 1 masz budżet 100 dolarów. Możesz kupić pierwsze i trzecie domy na 20 + 40 = 60 dolarów. W przykładowym przypadku # 2 masz budżet 50 dolarów. Możesz kupić 1st, 3 i 4 domy na 30 + 10 + 10 = 50 dolarów. W przypadku próbki # 3 masz budżet 300 dolarów. Nie możesz kupić żadnych domów (więc odpowiedź brzmi 0).

Oto moje rozwiązanie w Pythonie 3:

for i in range(int(input())):
    n, b = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    num = 0
    count = 0
    while num < b:
        num += a[count]
        count += 1
    thei = i + 1
    if num == b:
        print("Case #" + str(thei) + ": " + str(count))
    else:
        cout = count - 1
        print("Case #" + str(thei) + ": " + str(cout))

Nie widzę w nim żadnego pomyłki, ale pokazuje mi "Re" (błąd środowiska wykonawczego)

błąd

1
Hanson Sin 20 październik 2020, 18:27

1 odpowiedź

Najlepsza odpowiedź

Problem występuje, gdy wszystkie domy można kupić i nadal masz budżet. W takim przypadku pętla while będzie kontynuowana, a a[count] będzie nieprawidłowym dostępem w a.

Bez modyfikowania więcej niż potrzeby, dodasz dodatkowy warunek w pętli while: and count < len(a). Musisz także zmienić stan if po pętli do if num <= b.

Inne rozwiązanie

Powyższe rozwiązuje problem. Nadal nazwy zmiennych nie są takie jasne; Istnieje powtórzenie kodu do wyjścia; Możemy to zrobić bez zmiennej num, jeśli zmniejszymy budżet w iteracjach; i dlaczego nie pętla for zamiast pętli while:

for case in range(int(input())):
    _, budget = map(int, input().split())
    prices = list(map(int, input().split()))
    prices.sort()
    for house, price in enumerate(prices):
        if budget < price:  # cannot buy this house
            break
        budget -= price
    else:  # all houses can be bought
        house = len(prices)
    print("Case #{}: {}".format(case + 1, house))
1
trincot 22 październik 2020, 05:27