Проблема с разделением художника

Постановка задачи:

Дилприт хочет покрасить дом своей собаки, в котором есть доски разной длины. Длина доски задается arr[i], где arr[] – массив из n целых чисел. Он нанял k художников для этой работы, и каждому художнику требуется 1 единица времени, чтобы нарисовать 1 единицу доски.

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

Примеры Тестовых примеров:

Ввод:

n arr[] = {5,10,30,20,15} Вывод: 35 Объяснение: Наиболее оптимальным способом будет: Распределение маляра 1: {5,10} Распределение маляра 2: {30} Распределение маляра 3: {20,15} Работа будет выполнена, когда все маляры закончат, т.е. в(5+10, 30,

Ввод:

n arr[] = {10,20,30,40} Вывод: 20

Подход:

Здесь сначала мы можем подумать об этой проблеме так. Предположим, что у нас есть разделы k – 1, и нам нужно установить разделитель k – 1, чтобы получить разделы k. Как мы можем это сделать? Мы можем поместить k-1-й, разделенный между i-м и i + 1-м элементом, где n. Пожалуйста, обратите внимание, что поместить его перед первым элементом – это то же самое, что поместить его после последнего элемента. Общая стоимость этого мероприятия может быть рассчитана как максимум из следующих: а) Стоимость последнего раздела: сумма(Ai..An ), где k-1-й делитель находится перед элементом i. b) Максимальная стоимость любого раздела, уже сформированного слева от k-1-го разделителя. Здесь a) можно узнать с помощью простой вспомогательной функции для вычисления суммы элементов между двумя индексами в массиве. Как это выяснить б) ? Мы можем заметить, что б) на самом деле состоит в том, чтобы разместить разделители k2 как можно более справедливо, так что это подзадача данной проблемы. Таким образом, мы можем записать оптимальное свойство подструктуры в виде следующего рекуррентного соотношения:

Примечание : Фото взято с сайта geeksforgeeks

Но при таком подходе мы получаем экспоненциальную временную сложность, и основная идея состоит в том, чтобы использовать двоичный поиск и оптимизировать сложность до nlogn

Подход С Использованием Двоичного Поиска

Мы видим, что максимально возможное значение в этом диапазоне является суммой всех элементов массива, и это происходит, когда мы выделяем 1 для всех разделов доски. Минимально возможное значение этого диапазона является максимальным значением массива max, так как при этом распределении мы можем выделить max одному художнику и разделить другие разделы таким образом, чтобы их стоимость была меньше или равна max и как можно ближе к max. Теперь, если мы рассмотрим, что мы используем x в приведенных выше сценариях, очевидно, что по мере увеличения значения в диапазоне значение x уменьшается и наоборот. Исходя из этого, мы можем найти целевое значение, когда и использовать вспомогательную функцию, чтобы найти x, минимальное количество художников, требуемое, когда задана максимальная длина участка, который может нарисовать художник.

Код:

class Solution{
    static long minTime(int[] arr,int n,int k){
        //code here
        long sum = getSum(arr);
        long max = getMax(arr);
        return binarySearch(arr, max, sum, k);
    }

    static long binarySearch(int [] arr, long low, long high, int k) {
        while (low < high) {
            long middle = low + (high - low) / 2;
            int painters = findPainters(arr, middle);
            if (painters <= k) {
                high = middle;
            }
            else {
                low = middle + 1;
            }
        }
        return low;
    }

    static int findPainters(int [] arr, long maxTime) {
        int painter = 1;
        long sum = 0;
        int length = arr.length;
        for (int i=0; i maxTime) {
                painter ++;
                sum = arr[i];
            }
        }
        return painter;
    } 

    static long getSum(int [] arr) {
        long total = 0;
        for (int number : arr) {
            total += number;
        }
        return total;
    }

    static long getMax(int [] arr) {
        long max = Integer.MIN_VALUE;
        for (int number : arr) {
            max = Math.max(max, number);
        }
        return max;
    }
}

Анализ сложности:

Временная сложность: O(nlogn), где n – длина входного массива

Сложность пространства: O(1), так как дополнительное пространство не используется.

Ссылки на Github:

Rohithv07/Код доступа

Проблемы с кодом, которые решены.

Проблемы с кодом, которые решены.

Rohith v 07/LeetCode Топ-интервьювопросы

Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode. Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode.

Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode. Leetcode Лучшие вопросы для интервью, обсуждаемые в Leetcode.

Также ответ на вопрос от CodeSignal.com: https://app.codesignal.com/

Оригинал: “https://dev.to/rohithv07/the-painter-s-partition-problem-oi2”