Диалог:USER: Ваша компания сортировала отходы долгие годы и вот теперь у вас есть полный…
- User
Диалог:USER: Ваша компания сортировала отходы долгие годы и вот теперь у вас есть полный склад с мусором m разных типов. Для каждого типа мусора известно какое количество килограмм такого мусора есть на складе. Теперь вам поручено упаковать весь этот мусор в n одинаковых мешков. Для обеспечения удобства транспортировки и отчетности сделать это нужно с некоторыми условиями:
в одном мешке может быть только один тип мусора; в каждом мешке должно быть целое количество килограмм мусора; максимальное количество мусора в одном мешке должно быть минимальным. Определите максимальное количество мусора в одном мешке при такой схеме упаковки мусора.
Входные данные В первой строке задается два целых числа n , m
( 1 ⩽ n ⩽ 10 9 ; 1 ⩽ m ⩽ 3 ⋅ 10 5 ; m ⩽ n ) — количество мешков для мусора и количество различных типов мусора на складе.
В следующих m строках заданы m целых чисел c 1 , c 2 , … , c m
( 1 ⩽ c i ⩽ 10 9 ) — количество мусора каждого типа. Число m i равно количеству мусора типа i в килограммах на складе.
Выходные данные Выведите одно целое число — максимальное количество мусора в одном мешке при такой схеме упаковки мусора.ASSISTANT:
- Assistant
Чтобы найти максимальное количество мусора в одном мешке при данных условиях, можно использовать бинарный поиск. Попробуем найти ответ, перебирая возможное максимальное количество мусора в одном мешке, и проверим, удастся ли нам распределить весь мусор по мешкам так, чтобы соблюдались все условия. Основная идея — если мы можем уместить весь мусор в мешки при некотором предполагаемом максимальном весе мусора в одном мешке, то это значит, что возможный ответ лежит в диапазоне от начала поиска до текущего предполагаемого максимального значения. Если мы не можем уместить весь мусор при этом предполагаемом значении, то ответ лежит в диапазоне от текущего предполагаемого значения до конца поиска.
Алгоритм таков:
-
Установим левую границу бинарного поиска
lравной 1 (минимально возможное количество мусора в мешке) и правую границуrравной сумме всего мусора (т.к. это абсолютный максимум, который может понадобиться, если всё будет запаковано в один мешок). -
В цикле, пока
lменьшеr:- Находим середину
midкак(l + r) / 2. - Проверяем, сможем ли мы распределить весь мусор по мешкам, если максимальное количество мусора в одном мешке будет равно
mid.- Это делается итерацией по всем типам мусора и делением их количества на
mid(получаем количество мешков, необходимое для каждого типа мусора). Если сумма нужных мешков для всех типов мусора не превышает общее допустимое количество мешковn, то это возможно.
- Это делается итерацией по всем типам мусора и делением их количества на
- Если распределить мусор возможно, смещаем правую границу на
mid, иначе смещаем левую границу наmid + 1.
- Находим середину
-
В конце
lбудет содержать искомый максимум.
Пример кода на Python:
def умещается(n, m, c, max_v_musora): nuzhno_meshkov = 0 for i in range(m): nuzhno_meshkov += -(-c[i] // max_v_musora) # Округление вверх return nuzhno_meshkov <= n def binarny_poisk_maximuuma(n, m, c): l, r = 1, sum(c) while l < r: mid = (l + r) // 2 if умещается(n, m, c, mid): r = mid else: l = mid + 1 return l n, m = map(int, input().split()) c = [int(input()) for _ in range(m)] print(binarny_poisk_maximuuma(n, m, c))Этот код сначала читает входные данные, затем использует бинарный поиск для нахождения максимального возможного количества мусора в одном мешке.
-