9020. Разбиение на k подмассивов

 

Задан массив из n элементов и число k. Разбейте заданный массив на k подмассивов (которые содержат в себе все элементы). Вычислим максимум среди сумм элементов всех k подмассивов. Разбиение следует провести так, чтобы это значение было как можно меньшим. Найдите этот максимум.

 

Вход. Первая строка содержит два числа n и k (n ≤ 106, 1 ≤ k ≤ n). Вторая строка содержит n целых чисел, каждое из которых по модулю не более 109.

 

Выход. Выведите наименьшее возможное значение среди максимумов сумм элементов всех k подмассивов.

 

Пояснение. Для первого примера оптимальным разбиением будет {1, 2}, {3}, {4}. Максимум сумм элементов среди всех подмассивов равен 4, который является наименьшим возможным для 3 подмассивов.

Для второго примера оптимальным разбиением будет {1, 2, 3, 4}, {2, 3, 4}, {2, 3, 1}. Максимум сумм элементов среди всех подмассивов равен 10, который является наименьшим возможным для 3 подмассивов.

 

Пример входа 1

Пример выхода 1

4 3

1 2 3 4

4

 

 

Пример входа 2

Пример выхода 2

10 3

1 2 3 4 2 3 4 2 3 1

10

 

 

РЕШЕНИЕ

бинарный поиск

 

Анализ алгоритма

Искомое оптимальное значение будем находить бинарным поиском. Очевидно, что оно не меньше 1 (числа в массиве натуральные) и не больше суммы всех чисел. Положим left = 1, right = сумма чисел в массиве. Тогда ответ лежит на промежутке [left; right].

Рассмотрим подзадачу: можно ли разбить массив на k подмассивов так, чтобы максимум сумм всех k подмассивов был не больше s0. Если массив содержит хотя бы один элемент, больший s0, то такое разбиение невозможно. Разбиваем исходный массив на подмассивы, сумма элементов которых не больше s0. Если таких подмассивов будет не более k, то разбиение возможно.

 

Пример

Рассмотрим во втором примере искомые разбиения на подмассивы для различных значений s0:

 

 

 

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

Объявим константу MAX = 106 и рабочий массив m.

 

#define MAX 1000000

int m[MAX];

 

Функция f возвращает 1, если можно разбить массив на k подмассивов так, чтобы максимум сумм всех k подмассивов был не больше s0.

 

int f(long long s0)

{

  long long sum = 0;

  int cnt = 1;

  for (int i = 0; i < n; i++)

  {

 

Если некоторый элемент массива больше s0, то разбиение невозможно.

 

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

 

Считаем сумму текущего подмассива.

 

    sum += m[i];

 

Как только текущая сумма станет больше s0, то количество подмассивов cnt увеличиваем на 1 и начинаем подсчет суммы следующего подмассива.

 

    if (sum > s0)

    {

      sum = m[i];

      cnt++;

    }

  }

 

Если массив можно разбить на не более чем k подмассивов, то его можно разбить и на k (k ≤ n) подмассивов.

 

  if (cnt <= k) return 1;

  return 0;

}

 

Основная часть программы. Читаем входные данные. В переменной right вычислим сумму чисел в массиве.

 

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

left = 1; right = 0;

for (i = 0; i < n; i++)

{

  scanf("%d", &m[i]);

  right += m[i];

}

 

Искомое наименьшее значение среди максимумов сумм подмассивов лежит на промежутке [left; right]. Запускаем бинарный поиск.

 

while (left < right)

{

  mid = (left + right) / 2;

  if (f(mid) == 1)

    right = mid;

  else

    left = mid + 1;

}

 

Выводим ответ.

 

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