Найти пару к наибольшему числу в списке не превышающее значение m/ решение задачи, продолжить код

Question

задача: На берегу реки стояли n рыбаков, все они хотели перебраться на другой берег. Одна лодка может выдержать не более m килограмм, при этом в лодку помещается не более 2 человек. Определите, какое минимальное число лодок нужно, чтобы перевезти на другой берег всех рыбаков В первую строку вводится число m (1 ≤ m ≤ 10e6) - максимальная масса, которую может выдержать одна лодка. Во вторую строку вводится число n (1 ≤ n ≤ 100) - количество рыбаков. В следующие N строк вводится по одному числу Ai (1 ≤ Ai ≤ m) - вес каждого путешественника. Программа должна вывести одно число - минимальное количество лодок, необходимое для переправки всех рыбаков на противоположный берег.

    max_massa = int(input())
    n = int(input())
    res = []
    cnt = 0
    if ((max_massa >= 1) and (max_massa <= 10**7)) and ((n >= 1) and (n <= 100)):
        for i in range(n):
            m_r = int(input())
            res.append(m_r)
    ret = (sorted(res))
    ret.reverse()
    print(ret)

#ТУТ НЕ МОГУ РАЗОБРАТЬСЯ КАК ИСКАТЬ ПАРЫ НАИБОЛЬШИХ ЧИСЕЛ

    for i in range(len(ret)):
        if (ret[i] + (ret[i+1])) < max_massa:
            cnt += 1
            print(ret)
        elif (ret[i] + (ret[i+1])) > max_massa:
                ret[i] + ((ret[i+1])+1)
                ret.pop(i)
                cnt += 1
            else:
               ret.pop(i)
               cnt += 1
        else:
            ret.pop(i)
            cnt += 1
        
        print (i)
    print (cnt)

Answer 1

Комментарии в коде

max_massa, n = int(input()), int(input())
fishers = sorted((int(input()) for _ in range(n)), reverse=True)  # собираем и сортируем рыбаков по убыванию веса
cnt, l, r = 0, 0, len(fishers) - 1  # счетчик лодок, левый указатель (на самых тяжелых рыбаков), правый указатель (на самых легких рыбаков)
while r >= l:  # пока остались неперевезенные рыбаки
    if fishers[l] + fishers[r] <= max_massa:  # если совокупный вес самого тяжелого и самого легкого (из оставшихся) рыбаков не превышает грузоподьемность лодки,
        r -= 1  # то сажаем легкого
    l += 1  # сажаем тяжелого (всегда)
    cnt += 1  # +1 лодка отгружена
print(cnt)

БЛОГ НА HUSL

Найти пару к наибольшему числу в списке не превышающее значение m/ решение задачи, продолжить код

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