1

Тема: Помогите с задачей

Подскажите, пожалуйста, как решить задачу, суть которой заключается в следующем: есть M свечей, длина каждой - Li. Нужно получить N свечей одинаковых размеров (как можно длиннее). Свечи можно разрезать на мелкие как заблагорассудится, но лепить их вместе, нельзя.

2

Re: Помогите с задачей

Двоичный поиск: будем искать двоичным поиском искомую длину. Тогда задача сводится к такой: по данной длине (обозначим её через X) проверить, можно ли получить >=N свечей этой длины. Для этого считаем сумму величин Li/X (округленных вниз) - это и есть максимальное количество свечей, которое можно получить с длиной X.

3

Re: Помогите с задачей

Спасибо, а как оптимально найти Х.

4

Re: Помогите с задачей

Двоичный поиск

Т.е. мы двоичным поиском побираем такое максимальное X, при котором ещё можно получить N свечей.

5 Отредактировано BVI94 (2012-07-03 20:16:47)

Re: Помогите с задачей

Тест N=4 M=3 Li = 1, 4, 2. Ответ 1,333... На его примере как реализовать поиск...

6

Re: Помогите с задачей

Делаем двоичный поиск.

Изначально мы только знаем, что ответ где-то между 0 и 4.
Возьмём середину этого отрезка: X=2. Тогда получим, что можно получить 1/2+4/2+2/2=3 свечи, что меньше N=4. Следовательно, дальше надо пробовать только более короткие свечи, т.е. теперь интервал поиска - это [0..2].

Снова возьмём середину: X=1. Получим 1/1+4/1+2/1=7 свечей, что больше N=4.
Следовательно, можно пробовать свечи и большей, чем 1, длины. Поэтому новый интервал поиска - это [1..2].

Возьмём X=1.5, посчитаем, и т.д.

Через достаточно большое количество шагов (скажем, 100) мы достаточно близко сойдёмся к искомому ответу 1.333333333.

7

Re: Помогите с задачей

Большое спасибо.