Олімпіада#7503

Олімпіада (Розбір)

Всього на змагання прибуло $s = \sum_{i = 1}^{n} a_{i}$ s = \sum_{i=1}^n a_i учасників. Оскільки кожна аудиторія обладнана $m$ комп'ютерами, потрібно принаймні $⌈ s / m ⌉$ кімнат.

Нехай $p$ — найбільша кількість учасників в одній команді (максимальне значення серед усіх чисел $a_{i}$ a_i). Якщо $p > ⌈ s / m ⌉$ p > ⌈s/m⌉, то потрібно принаймні $p$ кімнат.

Конструктивно можна показати, що завжди достатньо $ma x (⌈ s / m ⌉, p)$ max(⌈s/m⌉, p) аудиторій для проведення олімпіади.

Приклад

На олімпіаду прибуло $2 + 3 + 4 + 1 + 2 = 12$ 2 + 3 + 4 + 1 + 2 = 12 школярів. Оскільки кожен клас обладнано $3$ комп'ютерами, для проведення олімпіади потрібно принаймні $12/3 = 4$ 12 / 3 = 4 класу.

Найбільша кількість учасників представляє третя команда — $4$ особи. Їх можна розсадити по одному в різні $4$ класи.

Наприклад, можлива наступна розсадка учасників:

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

Читаємо вхідні дані.

scanf("%d %d",&n,&m);

Обчислюємо загальну кількість учасників $s$ , а також розмір $p$ найбільшої команди.

p = 0;
for (i = 0; i < n; i++)
{
  scanf("%d",&x);
  s += x;
  if (x > p) p = x;
}

C++

Значення $r es = ⌈ s / m ⌉$ res = ⌈s/m⌉ обчислюємо як $(s + m - 1) / m$ (s + m - 1) / m.

res = (s + m - 1) / m;

Якщо $p > ⌈ s / m ⌉$ p > ⌈s/m⌉, то відповіддю буде $p$ .

if (res < p) res = p;

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

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