Блог

Основываясь на онлайн-решениях, я почти понял, как решить MinMaxDivision Codility, но в решении есть одна деталь, которую я изо всех сил пытаюсь подтвердить.

Вопрос заключается в следующем:

Описание задачи

Вам даны целые числа K, M и непустой массив A, состоящий из N целых чисел. Каждый элемент массива не больше M.

Вы должны разделить этот массив на K блоков последовательных элементов. Размер блока равен любому целому числу от 0 до N. Каждый элемент массива должен принадлежать некоторому блоку.

Сумма блока от X до Y равна A[X] A [X 1] … A [Y] . Сумма пустого блока равна 0.

Большая сумма — это максимальная сумма любого блока.

Например, вам даны целые числа K = 3, M = 5 и массив A такой, что:

 A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2  
A[6] = 2
 

Массив может быть разделен, например, на следующие блоки:

 [2, 1, 5, 1, 2, 2, 2], [], [] with a large sum of 15;
[2], [1, 5, 1, 2], [2, 2] with a large sum of 9;
[2, 1, 5], [], [1, 2, 2, 2] with a large sum of 8;
[2, 1], [5, 1], [2, 2, 2] with a large sum of 6.
 

Цель состоит в том, чтобы минимизировать большую сумму. В приведенном выше примере 6 — это минимальная большая сумма.

Напишите функцию:

 class Solution { public int solution(int K, int M, int[] A); }
 

это, учитывая целые числа K, M и непустой массив A, состоящий из N
целых чисел, возвращает минимальную большую сумму.

Например, учитывая K = 3, M = 5 и массив A такой, что:

 A[0] = 2
A[1] = 1
A[2] = 5
A[3] = 1
A[4] = 2
A[5] = 2  
A[6] = 2
 

функция должна возвращать 6, как объяснено выше.

Напишите эффективный алгоритм для следующих предположений:

• N и K — целые числа в диапазоне [1..100 000]; M — целое число
• в пределах диапазона [0..10 000]; каждый элемент массива A является целым числом
• в пределах диапазона [0 ..M].

Следующее решение получает 100%:

 public int solution(int K, int M, int[] A) {

    int min = 0;
    int max = 0;

    for (int i = 0; i < A.length; i  ) {
        max  = A[i];
        min = Math.max(min, A[i]);
    }

    if (K == 1)
        return max;

    if (K >= A.length)
        return min;

    int result = min;

    while (min <= max) {

        int mid = (min   max) / 2;

        if (check(mid, K, A)) {

            max = mid - 1;
            result = mid;

        } else {

            min = mid   1;

        }

    }

    return resu<
}

private boolean check(int mid, int k, int[] a) {

    int sum = 0;

    for (int i = 0; i < a.length; i  ) {

        sum  = a[i];

        if (sum > mid) {
            sum = a[i];
            k--;
        }

        if (k == 0)
            return false;

    }

    return true;

}
 

Идея решения довольно проста: минимальная большая сумма находится между min (A) или sum (A) . Вместо того, чтобы повторять один за другим, мы можем использовать двоичный поиск для поиска минимальной большой суммы. Для каждого кандидата (mid) мы видим, можем ли мы иметь K блоков, которые не передают значение mid.

Мой вопрос касается стратегии определения количества блоков на основе среднего значения в методе check() выше. Бывают ситуации, когда количество блоков соответствует критериям, но ни у одного из блоков сумма не равна среднему значению. Один хороший пример — когда у нас есть один блок со всеми значениями массива, а остальные блоки пусты.

Одним из хороших примеров является = [2, 3, 3, 5, 4, 2, 3], K = 3: среднее значение, которое в конечном итоге получим, равно значению 10, у нас может быть 3 блока [2,3,3],[5,4],[2,3] но ни один из них не равен 10.

Может ли алгоритм решения вывести среднее значение, являющееся минимальной большой суммой, но эта сумма на самом деле не существует? Как метод check() может всегда находить минимальную большую сумму, И эта минимальная большая сумма существует в массиве, не сравнивая значение суммы со средним значением?

Бывают ситуации, когда количество блоков соответствует критериям, но ни один из блоков не имеет суммы, равной среднему значению

Это не имеет значения, потому check что вернется true , и mid будет проверено значение lower: некоторое значение lower mid в конечном итоге будет равно сумме некоторого блока.

Одним из хороших примеров является = [2, 3, 3, 5, 4, 2, 3], K = 3: среднее значение, которое в конечном итоге получим, равно значению 10, у нас может быть 3 блока [2,3,3],[5,4],[2,3] но ни один из них не равен 10.

После mid = 10 и check возврата true это будет выполнено:

 max = mid - 1;
result = mid;
 

Установив значение max 9 , 9 в конечном итоге оно также будет проверено и будет возвращено.

Может ли алгоритм решения вывести среднее значение, являющееся минимальной большой суммой, но эта сумма на самом деле не существует?

Нет, потому что, если эта сумма не существует и check возвращается true , тогда у нас есть меньшая сумма, которая возможна, поэтому ток mid не является минимальным. Если алгоритм получит 100%, он выведет это меньшее значение.

Также подумайте об этом с точки зрения определения, данного в постановке задачи:

Большая сумма — это максимальная сумма любого блока.

[…]

Цель состоит в том, чтобы минимизировать большую сумму. В приведенном выше примере 6 — это минимальная большая сумма.

Итак, по определению, минимальная большая сумма — это сумма некоторого блока.

Как метод check() может всегда находить минимальную большую сумму, И эта минимальная большая сумма существует в массиве, не сравнивая значение суммы со средним значением?

Сам check метод не находит минимально большую сумму. Он только сообщает вам, является ли заданная сумма (ее mid параметр) допустимой (то есть, можем ли мы разделить массив на K блоки с максимальной суммой <= mid ).

Это двоичный поиск, который находит минимальную большую сумму.