Найдите максимально возможную площадь пиццы

[Linok0036]

Нужно написать код на с++, вот задачка:
В данный момент в пиццерии готово n пицц. У каждой пиццы есть соответствующий диаметр R и цена S. Любой посетитель пиццерии может взять любую пиццу или ее часть. После того, как посетитель возьмет всю пиццу, он заплатит за нее полную стоимость, но если он возьмет часть пиццы, то заплатит только за соответствующую часть (например, взяв треть пиццы, вы заплатите треть цены).

В данный момент у Ивана x денег и он хочет съесть как можно больше пиццы. Какую максимальную площадь пиццы может съесть Иван за заданную сумму денег? Используйте дробь 355/113 вместо числа pi.

Входные данные: первая строка содержит два целых числа n и x (0 ≤ n ≤ 1000, 0 ≤ x ≤ 10^9). Следующие строки содержат два целых числа R и S (1 ≤ R, S ≤ 10^6).
Выходные данные: выведите максимально возможную площадь пиццы, оставив три цифры после десятичной точки.

Например
Если ввести:
5 20
4 12
3 5
6 7
3 6
7 3
То ответ должен быть 79.718

[macomics]

Странно: (79.718 * 113 / 355)^1/2 = 5.03736293631
Но если взять только последнюю пиццу 7 3, то радиус у неё 7, а стоимость 3. т.е. останется ещё 17 деньгами, чтобы нажраться до отвала.
Если решать самым простым и понятным способом эту задачу, то у меня получилась площадь 1075.21017699 аж в 13,5 раз больше (по сумме радиусов 18.5 вместо 5)

[ViktorR]

1. Определяем цену куска пиццы: R^2 / S (pi пока не учитываем).
Сколько пиццы можно купить на один золотой.

В соответствии с примером получим:

 5 20
1. 4 12   16 / 12 ~= 1.33
2. 3 5     9 / 5  ~= 1.8
3. 6 7    36 / 7  ~= 5.14
4. 3 6     9 / 6   = 1.5
5. 7 3    49 / 3  ~= 16.3

2. Теперь набираем от самой дешёвой к дорогой:

5-я по 3  вся +  (3)
3-я по 7  вся +  (3 + 7 =10)
2-я по 5  вся +  (3 + 7 + 5 = 15)
4-я по 6  5/6-х  (3 + 7 + 5 + 5 = 20)

ИТОГО: S = (49 + 36 + 9 + 9*5/6)*pi ~= 318,872.

Возможно, что ТС ошибся и дан не радиус пиццы, а её диаметр.
В этом случае: S = pi*D^2/4. Т.е., наш результат надо делить на 4-е.
S = 318,872 / 4 = 79,718

[BDA]

Сообщение от ViktorR

дан не радиус пиццы, а её диаметр.

Ага, в условии так и написано "диаметр" (но авторы обозначили его буквой R: или чтобы проверить на внимательность, или при изменении условия забыли R на D поправить).

[ViktorR]

Пока читал и решал задачу забыл условие (сбился из-за буквы). А потом и не проверил.
Стар стал, ...

[macomics]

Тоже самое...

[ViktorR]

Решил не останавливаться. На С++ ???
Вот на Python:

def max_area_pizza(m, x):
    pi = 355 / 113      # Число pi
    n = len(m)          # Всего пиццы
    P = 0               # Площадь съеденой пиццы
    if x and n:         # Деньги есть и есть пицца
        m_d = []        # Доля пиццы за единицу денежки: показатель - отношение диаметра к цене
        for k in range(n):
            m_d.append(m[k][0] / m[k][1])
        # Сортируем полученный список по убыванию значений и сохраняем индексы элементов
        l_i = [k[0] for k in sorted(enumerate(m_d), key=lambda x:x[1], reverse=True)]
        # l_i - отсортированный список индексов.
        # Сортировка выполнена по площади пиццы за еденицу денежки.
        # Т.о., первый элемент списка - индекс на самую дешовую пиццу (самая большая порция пиццы за единицу денежки)
        
        # enumerate(m) - вернёт список с вложенными кортежами вида (i, x): [(0, x), (1, x), ...(i, x)],
        # где i - индекс элемента, x - значение элемента;
        #
        # лямда-функция передаст функции sorted() на сортировку значения элементов.
        #
        # Сортировка будет выполнена по убыванию значений: reverse=True.
        # По умолчанию установлено reverse=False - сортировка по возрастанию
        
        tS = 0                             # съедено пиццы на сумму tS
        for i in range(n):
            tS += m[l_i[i]][1]             # Набираем цену: выбираем цену по номеру пиццы
            if tS > x:                     # Перебор
                tS -= m[l_i[i]][1]         # Правим сумму и
                break                      # завершаем набор
            P += m[l_i[i]][0]**2           # Подсчитываем сумму площадей
        
        if tS < x:                         # Недобор. От i-ой пиццы надо взять площадь на остаток суммы
            dS = x - tS                    # Остаток суммы.
            # Нам надо взять долю - dS / DS[i][1]
            dP = m[i][0]**2 * dS / m[i][1]  # Доля площади от пиццы, на которой был перебор
            P = P + dP                     # Итого
    return P * pi / 4


n = 5
x = 20
# Список пиццы: (Диаметр, Цена)
DS = [(4, 12), (3, 5), (6, 7), (3, 6), (7, 3)]  

P = max_area_pizza(DS, x)
if P:
    print(f'ИТОГО: {P : 14.3f}')
else:
    print('P = 0, так как нет денег или пиццы!')

[BDA]

ViktorR, я бы не стал мучаться с массивом индексов и делать сложную индексацию, а отсортировал бы сам массив:

def max_area_pizza(m, x):
    pi = 355 / 113
    P = 0
    tS = 0
    for D, S in sorted(m, key = lambda x: x[1] / x[0]):
        if tS + S > x:
            if tS < x:
                P += D**2 * (x - tS) / S
            break
        tS += S
        P += D**2
    return P * pi / 4

[ViktorR]

Позже подумал и сделал через zip(), но ваш вариант лучше.
Спасибо, учимся ...

PS: Пока у меня нет должного понимания лямбда-функций

PSS: Мне понравилось, как учтён случай набора целых пицц.