Задача 81: Мелодия

Условие задачи:

Юные физики Евгений и Родион очень любят музыку, кроме того Родион умеет исполнять любое произведение при помощи бутылок с водой. У них есть \(N\) бутылок бесконечной вместимости. В \(i\)-ой бутылке уже содержится \(a_i\) мл воды. Также у них есть бочонок с \(L\) мл воды, из которого можно переливать любой имеющийся объём воды в любую бутылку. Выливать воду из бутылок нельзя. После того как Евгений заканчивает все переливания, он больше не притрагивается к бутылкам, а Родион начинает играть мелодию.

Мелодия состоит из \(M\) нот \(b_1,b_2,\ldots,b_M\), которые обязательно надо исполнять в заданном порядке. Ноту \(b_i\) Родион сможет сыграть, если найдется бутылка с \(b_i\) мл воды. Если очередную ноту он исполнить не может, то сильно огорчается и перестает играть. Евгений стремится наполнить бутылки таким образом, чтобы Родион играл как можно дольше. Помогите ребятам узнать, какое максимальное количество начальных нот данной мелодии сможет сыграть Родион при оптимальных действиях Евгения.

Входные данные:

В первой строке входного файла содержатся три целых числа \(N, M, L\) - количество бутылок, длина мелодии и объем бочонка соответственно. Во второй строке через пробел расположены \(N\) чисел \(a_i (i=1,2,…N)\) - количество мл в \(i\)-ой бутылке. В третьей строке - \(M\) чисел \(b_i (i=1,2,…M)\) - последовательность нот в мелодии (каждая музыкальная нота обозначается своим числом, одинаковые ноты - одинаковыми числами). Все числа целые и неотрицательные.

Выходные данные:

Выведите единственное число - максимальное количество начальных нот мелодии, которые можно сыграть, оптимально заполнив бутылки.

Решение:

N, M, L = map(int, input().split())
bottles = sorted(list(map(int, input().split())))
notes = list(map(int, input().split()))


def get_nearest(x):
    l = 0
    r = len(bottles)
    while r - l > 1:
        m = (r + l) // 2
        if x >= bottles[m]:
            l = m
        else:
            r = m
    if r == 0:
        return False, 0
    return bottles[l] + L >= x >= bottles[l], l


ans = 0
um = set()
for i in notes:
    if i in um:
        ans += 1
        continue
    s, d = get_nearest(i)
    if not s:
        break
    L -= (i - bottles[d])
    bottles.pop(d)
    ans += 1
    um.add(i)

print(ans)

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик