5363. Сушка
Очень трудно
стирать и особенно сушить белье в зимний период. Но Джейн очень умная девочка.
Она не боится этого скучного процесса. Для ускорения процесса сушки Джейн
решила использовать радиатор. Однако радиатор мал, и способен выдержать в
каждый момент времени только одну вещь.
Джейн хочет
выполнить сушку в минимально возможное время. Она просит Вас написать
программу, которая вычислит минимальное время сушки для данного набора одежды.
Джейн только что
постирала n вещей. Во время стирки
каждая из них набрала ai
единиц воды. Каждую минуту количество воды в каждой вещи уменьшается на единицу
(если конечно же вещь не является полностью сухой). Когда количество воды в
вещи становится нулевым, вещь становится сухой и ее можно упаковывать.
Каждую минуту
Джейн может выбрать одну вещь, которую может положить на батарею. Батарея
достаточно горячая, поэтому каждую минуту на ней вещь теряет k единиц воды (но не меньше нуля – если вещь
содержит менее k единиц воды, то
через минуту воды в ней будет ноль).
Задача состоит в
том, чтобы минимизировать общее время сушки с помощью эффективного
использования радиатора. Процесс сушки заканчивается, когда вся одежда сухая.
Вход. Первая строка содержит одно число n (1 ≤ n ≤ 105). Вторая строка
содержит числа ai (1
≤ ai ≤ 109).
В третьей строке находится число k (1
≤ k ≤ 109).
Выход. Выведите одно число – наименьшее количество минут, за
которое можно высушить все белье.
|
Пример
входа |
Пример
выхода |
|
3 2 3 9 5 |
3 |
РЕШЕНИЕ
бинарный
поиск
Анализ алгоритма
Пусть max – наибольшее число среди ai. Очевидно, что через max минут все белье высохнет само собой,
если не использовать радиатор.
Пусть ответом
является значение m. Это значит что
белье, имеющее в себе объем воды, не больший m, высохнет само. Если белье содержит воды больше чем m, то его следует класть на батарею.
Будем считать,
что любое белье в одну минуту теряет 1 единицу воды (независимо от того
находится ли оно на батарее или нет), а в случае если его кладут на батарею –
то оно к 1 единице воды
еще дополнительно теряет k – 1 единицу
воды.
Если для сушки
белья достаточно m минут, то каждую
вещь, содержащую в себе более m
единиц воды, следует класть на батарею. При этом если она содержит ai > m единиц воды, то разность ai
– m следует высушивать на батарее, на
что уйдет 
минут. При этом
количество сушек 
должно быть не больше m (суммирование берется по всем индексам
i, для которых ai > m).
Значение m ищем бинарным поиском.
Пример
Изначально
имеются три вещи, (2, 3, 9) – количество воды в каждой из них.
В первую минуту
положим третью вещь на батарею, получим (1, 2, 4).
Во вторую минуту
положим третью вещь на батарею, получим (0, 1, 0).
В третью минуту
вторая вещь высохнет сама, (0, 1, 0).
Если положить m = 2 минуты, то высушить следует 3 – 2
= 1 единицу воды из первой вещи и 9 – 2 = 7 единиц воды со второй вещи. На что
потребуется 
= 3 минуты. Это больше
чем m = 2. Следовательно двух минут
недостаточно.
Реализация алгоритма
Объявим рабочий
массив.
#define MAX 100001
int a[MAX];
Читаем входные данные.
scanf("%d",&n);
for(i = 0; i < n; i++) scanf("%d",&a[i]);
scanf("%d",&k);
За r минут все
белье обязательно высохнет даже без использования батареи.
l = 0; r =
*max_element(a,a+n);
Если k ≤ 1,
то сушка с использованием радиатора эквивалентна сушке без него.
if (k <= 1)
{
printf("%d\n",r);
return 0;
}
Ищем наименьшее количество минут m на промежутке [l; r] бинарным поиском.
while(r - l > 1)
{
m = (r + l) / 2; dry = 0;
for(i = 0; i < n; i++)
{
if (a[i]
> m)
dry += (a[i] - m + k - 2) / (k - 1);
if (dry
> m) break;
}
if (dry >
m) l = m; else r = m;
}
Выводим ответ.
printf("%d\n",r);