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

Давайте поможем некоторым художникам качественно закончить свою работу!

Задача:
Учитывая количество маляров и несколько досок, мы должны найти минимальное время, за которое маляры могут покрасить эти доски.

Условия:
1. Одна доска не может быть частично окрашена более чем одним маляром.
2. Один маляр может красить только смежные доски.

Входные данные
A : количество маляров
B : время, затрачиваемое одним маляром на покраску одной единицы доски
C : массив досок по длине

Вывод:
Минимальное время, необходимое для покраски всех досок.

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

Примеры:

Пример 1
A = 2 | В = 5 | С = [1, 10]

Так как с нами два маляра, а досок всего две, то варианты следующие:
1. Один маляр покрасит обе доски, т.е. 11 единиц времени = 11*5 = 55
2 Один маляр красит первую доску, затрачивая на это 1*5=5 единиц времени. Второй маляр красит вторую доску, затрачивая 10*5 = 50 единиц времени.
Минимальное время, необходимое для покраски всех досок = 50

Пример 2
A = 10 | В = 1 | С = [1, 8, 11, 3]

Поскольку с нами 10 маляров, что больше, чем количество досок, которые у нас есть, мы можем выделить по одному маляру на каждую доску.
P1 рисование C1, время = 1*1 = 1
P2 рисование C2 , занимая время = 8*1 = 8
P3 рисование C3, занимая время = 11*1 = 11
P4 рисуя C4, занимая время = 3*1 = 3
Минимальное время, которое потребуется покрасить все доски = 11

Пример 3
A = 1 | В = 5 | С = [2,7,9,1]

Поскольку с нами только один маляр, все доски должен быть окрашен одним и тем же маляром, что оставляет нам только одну возможность.
Время, затраченное маляром = (2+7+9+1)*5 = 85

Наблюдения:

1. Если у нас есть неограниченное количество маляров, то минимальное время, за которое все маляры покрасят все доски, будет равно покраске доски максимальной длины.
2. Если у нас есть только один маляр, то этот человек должен покрасить все доски, поэтому минимальное время, которое потребуется, будет суммой длин досок, умноженной на время, необходимое для покраски одной единицы.

Подход:

Верхним пределом минимального времени будет время, когда один маляр должен покрасить все доски. Нижний предел минимального времени будет иметь место, когда доступно неограниченное количество маляров, а минимальное время будет ограничено временем, затрачиваемым на покраску доски максимальной длины.

Поскольку нам нужно найти минимальное время, необходимое для покраски всех досок, и мы знаем верхний и нижний предел минимального времени, мы можем выполнить «бинарный поиск» по единицам доски для рисования, основываясь на следующих наблюдениях за монотонностью. :

Учитывая число, которое представляет максимальное количество единиц, которые может покрасить один маляр, и мы находим количество маляров, необходимых для покраски всех досок с этим условием:

1. Если количество художников больше, чем доступных художников (A), это означает, что если мне нужно работать с несколькими художниками, я должен увеличить этот предел максимального количества единиц, которые можно рисовать.
2. Если количество художников меньше, чем доступных художников (A), это означает, что я могу попросить художников A сделать то же самое с меньшим пределом максимального количества единиц, которые можно нарисовать.
3. Если количество маляров равно количеству доступных маляров (A), то я также могу спросить, могут ли маляры A покрасить все доски с меньшим лимитом на одном маляре, что, в свою очередь, приведет к тому, что одному маляру будет дано меньше единиц краски. и сократить время покраски.

Псевдокод:

int paint(int A, int B, int[] C) {
    low = getMax(C); // lower limit of min time
    high = getSum(C); // upper limit of min time
    while (low < high) {
        mid = (low + high) / 2;
        // get number of painters with max paint limit as mid
        n = getPaintersWithLimit(C, mid);
        if (A < n) 
            low = mid + 1;
        else 
            high = mid;
    }
    return getTimeForUnits(low);
}

Решение: