Будівництво (Розбір)

Будемо шукати довжину містка $d$ за допомогою бінарного пошуку. Спочатку покладемо d \in [Left; Right] = [0; INF].

Розглянемо наступну підзадачу: чи можна скласти потрібний місток довжини точно Mid = (Left + Right) / 2? Для цього порахуємо, скільки дощок довжини $Mid$ можна отримати з наявних.

З дошки довжини l_i можна отримати \lfloor l_i / Mid \rfloor дощок довжини $Mid$. Просумувавши це значення по всіх дошках, дізнаємося загальну кількість дощок довжини $Mid$, які можна отримати розрізанням:

Якщо загальна кількість таких дощок не менша $m$, то це означає, що можна спробувати збільшити довжину — встановлюємо Left = Mid + 1. Інакше зменшуємо верхню межу: Right = Mid.

Відповіддю на задачу буде значення Left - 1.

Приклад

У наведеному прикладі є $4$ дошки. Необхідно побудувати місток, що складається з $6$ дощок. Якщо обрати довжину дошки рівною $8$, то з наявних дощок можна отримати

дощок довжини $8$.

Якщо ж обрати довжину $9$, то вийде

дощок, що менше необхідної кількості.

Реалізація алгоритму

Визначимо використовувані константи. Довжини наявних дощок l_i зберігаємо в масиві $a$.

#define INF 2000000010
#define MAX 1000009
long long a[MAX];

Функція cnt повертає кількість дощок, яке можна отримати з наявних, якщо кожна з них повинна мати довжину точно $Mid$. Це значення дорівнює сумі

long long cnt(long long  Mid) 
{
  if (Mid == 0) return INF;
  long long res = 0;
  for(i = 0; i < n; i++)
    res += a[i] / Mid;
  return res;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d %d",&n,&m);
for(i = 0; i < n; i++)
  scanf("%d",&a[i]);

Встановимо межі для значення d \in [Left; Right] = [0; INF] і запустимо бінарний пошук.

Left = 0;
Right = INF;
while (Left < Right)
{
  Mid = (Left + Right) / 2;

Значення cnt(Mid) дорівнює кількості дощок, яке можна отримати з наявних, якщо кожна з них повинна мати довжину $Mid$. Якщо ця кількість менша за потрібне число $m$, слід зменшити передбачувану довжину дошки: встановлюємо Right = Mid. Інакше збільшуємо ліву межу: Left = Mid + 1.

  if (cnt(Mid) < m) Right = Mid;
  else Left = Mid + 1;
}

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

printf("%lld\n",Left - 1);