Python-сообщество

udeep · Ноя. 25, 2019 20:42:49

Условие:
Greedy
Little Johnny eats fruits from his grandma's basket. There are fruits with different mass in this basket. Little Johnny can pick up not more than K ounces. Each fruit weights not more than K ounces. At a time, he chooses a few of the most heavy fruits, which he can pick up simultaneously, bites a half of each of them and puts what is left back into the basket. If the fruit weights odd number of ounces, he bites off its half, rounded up to the nearest whole number. He completely eats those fruits, which weight 1 ounce.
Find the number of attempts Little Johnny needs in order to eat all fruits in the basket.

Write your heap storage class, which implements priority queue.

Input data format. Integer n – the number of fruits, and the line with integer masses of fruits separated by space. Then in the separate line - the “lifting capacity”.
Output data format. A non-negative number – the number of attempts to the basket.

Мое решение:

  
import heapq
 
 
class heap_storage(list):
    def assign(self, array):
        super().extend(-v for v in array)
        heapq.heapify(self)
 
    def heappop(self):
        heapq.heappop(self)
 
    def heappush(self, v):
        heapq.heappush(self, -v)
 
    def get_max(self):
        return -self[0]
 
 
_ = input()
b = heap_storage()
b.assign(map(int, input().split()))
k = int(input())
 
z = 0
while b:
    r = 0
    while b:
        v = b.get_max()
        r += v
        if r > k:
            break
        b.heappop()
        if v > 1:
            b.heappush(v >> 1)
    z += 1
    
print(z)

Решение соответствует Тесту #8:
Вход:
20
2 10 23 23 2 18 19 8 14 19 14 13 20 1 23 6 5 1 3 8
23
Ожидаемый ответ:
22

Решение соответствует Тесту #5:
Вход:
10
1 10 2 9 3 8 4 7 5 6
10
Ожидаемый ответ:
11

Но не проходит Тест #2, входные данные которого мне, увы, не известны.
PS. “Голову сломал”…

Уже подсказали… Всем спасибо.
Исправленное решение:

  
import heapq
  
  
class heap_storage(list):
    def assign(self, array):
        super().extend(-v for v in array)
        heapq.heapify(self)
  
    def heappop(self):
        heapq.heappop(self)
  
    def heappush(self, v):
        heapq.heappush(self, -v)
  
    def get_max(self):
        return -self[0]
  
  
_ = input()
b = heap_storage()
b.assign(map(int, input().split()))
k = int(input())
 
z = 0
while b:
    r = 0
    a = []
    while b:
        v = b.get_max()
        r += v
        if r > k:
            break
        b.heappop()
        if v > 1:
            a.append(v >> 1)
    z += 1
    for v in a:
        b.heappush(v)
    
print(z)

Отредактировано udeep (Ноя. 25, 2019 22:23:13)

Python-сообщество

Уведомления

#1 Ноя. 25, 2019 20:42:49

Задача по алгоритму Greedy - помогите, pls, найти ошибку...

Board footer