Розбиття на k підмасивів#9020

Розбиття на k підмасивів (Розбір)

Будемо шукати оптимальне значення за допомогою бінарного пошуку. Очевидно, що воно не може бути менше $1$ (оскільки числа в масиві натуральні) і не може перевищувати суму всіх елементів масиву. Встановимо межі: $l e f t = 1, r i g h t$ left = 1, right = сума всіх чисел масиву. Тоді відповідь гарантовано знаходиться в діапазоні $[l e f t; r i g h t]$ [left; right].

Розглянемо допоміжну підзадачу: чи можна розбити масив на $k$ підмасивів так, щоб максимальна сума серед усіх $k$ підмасивів не перевищувала заданого значення $s_{0}$ s_0. Якщо в масиві є хоча б один елемент, що перевищує $s_{0}$ s_0, таке розбиття неможливе. В інших випадках будемо послідовно формувати підмасиви з сумою елементів, що не перевищує $s_{0}$ s_0. Якщо в результаті отримаємо не більше $k$ підмасивів, то таке розбиття можливе.

Приклад

У другому прикладі розглянемо можливі розбиття масиву на підмасиви при різних значеннях $s_{0}$ s_0:

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

Оголосимо константу $M A X = 1 0^{6}$ MAX = 10^6 і робочий масив $m$ .

#define MAX 1000000
int m[MAX];

Функція f повертає $1$ , якщо масив можна розбити на $k$ підмасивів так, щоб максимальна сума серед усіх $k$ підмасивів не перевищувала заданого значення $s_{0}$ s_0.

int f(long long s0)
{
  long long sum = 0;
  int cnt = 1;
  for (int i = 0; i < n; i++)
  {

Якщо якийсь елемент масиву більше $s_{0}$ s_0, то таке розбиття неможливе.

    if (m[i] > s0) return 0;

Обчислюємо суму поточного підмасиву.

    sum += m[i];

Як тільки поточна сума перевищує значення $s_{0}$ s_0, збільшуємо лічильник підмасивів $c n t$ на $1$ і починаємо накопичувати суму наступного підмасиву.

    if (sum > s0)
    {
      sum = m[i];
      cnt++;
    }
  }

Якщо масив можна розбити не більше ніж на $k$ підмасивів, значить, його можна розбити і точно на $k (k \leq n)$ k~(k \le n) підмасивів.

  if (cnt <= k) return 1;
  return 0;
}

Основна частина програми. Читаємо вхідні дані. У змінній $r i g h t$ обчислюємо суму всіх елементів масиву.

scanf("%d %d", &n, &k);
left = 1; right = 0;
for (i = 0; i < n; i++)
{
  scanf("%d", &m[i]);
  right += m[i];
}

C++

Шукане мінімальне значення максимальної суми підмасивів знаходиться в діапазоні $[l e f t; r i g h t]$ [left; right]. Запускаємо бінарний пошук на цьому відрізку.

while (left < right)
{
  mid = (left + right) / 2;
  if (f(mid) == 1)
    right = mid;
  else
    left = mid + 1;
}

C++

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

printf("%lld\n", left);