Сушіння#5363

Сушіння (Розбір)

Нехай $ma x$ — найбільше значення серед усіх $a_{i}$ a_i. Очевидно, що через max хвилин уся білизна висохне самостійно, навіть без використання радіатора.

Нехай відповідь дорівнює $m$ . Це означає, що вся білизна, яка містить не більше $m$ одиниць води, встигне висохнути природним шляхом. А речі, в яких води більше $m$ , потрібно додатково сушити на радіаторі.

Будемо вважати, що кожна річ втрачає по одній одиниці води на хвилину, незалежно від того, знаходиться вона на радіаторі чи ні. Якщо ж річ кладуть на радіатор, то вона втрачає додатково ще $k - 1$ k - 1 одиниць води на хвилину, тобто всього $k$ одиниць на хвилину.

Якщо для сушки всіх речей достатньо $m$ хвилин, то кожну річ з $a_{i} > m$ a_i > m необхідно додатково сушити на радіаторі. Обсяг води, який не встигне випаруватися природним шляхом, становить $a_{i} - m$ a_i - m. За одну хвилину радіатор видаляє додатково $(k - 1)$ (k - 1) одиниць води, тому на таку річ потрібно

⌈ \frac{a _{i} - m}{k - 1} ⌉

\left\lceil {a_i - m \over k - 1} \right\rceil

хвилин радіаторного часу.

Сумарна кількість хвилин $i = 1 \sum n ⌈(a_{i} - m) / (k - 1)⌉$ \displaystyle \sum_{i=1}^n \lceil (a_i - m) / (k - 1) \rceil використання радіатора не повинна перевищувати $m$ , оскільки в кожну хвилину можна сушити лише одну річ. Підсумовування береться по всіх індексах $i$ , для яких $a_{i} > m$ a_i > m.

Таким чином, перевірка здійснюється наступним чином: якщо для заданого $m$ загальна кількість необхідних хвилин сушки на радіаторі не перевищує $m$ , то значення $m$ допустиме. Найменше підходяще значення $m$ ми шукаємо за допомогою бінарного пошуку.

Приклад

Спочатку є три речі з кількістю води $(2, 3, 9)$ (2, 3, 9).

У першу хвилину кладемо третю річ на радіатор. Після цього отримуємо: $(1, 2, 4)$ (1, 2, 4).

У другу хвилину знову кладемо третю річ на радіатор. Стан стає $(0, 1, 0)$ (0, 1, 0).

На третій хвилині друга річ висихає сама. Кінцевий стан: $(0, 0, 0)$ (0, 0, 0).

Розглянемо значення $m = 2$ m = 2. Тоді всі речі, що містять не більше $2$ одиниць води, висохнуть самі.

Для решти потрібна сушка на радіаторі. Друга річ містить $3$ одиниці води, отже, на радіаторі потрібно видалити $3 - 2 = 1$ 3 - 2 = 1 одиницю.

Третя річ містить $9$ одиниць, тому на радіаторі потрібно видалити $9 - 2 = 7$ 9 - 2 = 7 одиниць води.

На це потрібно $⌈ 1/4 ⌉ + ⌈ 7/4 ⌉ = 3$ \lceil 1/4 \rceil + \lceil 7/4 \rceil = 3 хвилини. Це більше ніж $m = 2$ 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 \leq 1$ k \le 1, то сушка з використанням радіатора еквівалентна природній сушці, і радіатор не дає жодної переваги.

if (k <= 1) 
{
  printf("%d\n",r); return 0;
}

Шукане мінімальне число хвилин m можна знайти бінарним пошуком на відрізку $[l; r]$ [l; r].

while (r - l > 1)
{
  m = (r + l) / 2;

Змінна $d r y$ накопичує загальну кількість хвилин, протягом яких потрібно використовувати радіатор. При цьому за $m$ хвилин слід висушити всю білизну.

  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;
}

C++

Виводимо відповідь.

printf("%d\n",r);