БЛОГ НА HUSL


Олимпиадная алгоритмическая задача

Автор вопроса: Артём

Прошу натолкнуть на решение задачи или подсказать что можно почитать/посмотреть на эту тему

Условие:

У вас есть n бревен, длина i-го бревна равна Ai

Вы можете выполнить следующую операцию не более К раз:

Выбрать одно и n бревен и разрезать его. Когда вы разрезаете бревно длины L на расстоянии t (0 < t < L, t может быть нецелым), от его конца, оно превращается в два бревна длины t и L-t соответсвенно.

Найдите минимальную длину самого длинного из бревен, после того как вы сделаете не более K операций. Полученое число округляем вверх!

Входные данные:

  1. В первой строке два числа n и k (ограницение на сами числа - миллиард) - кол-во бревен и разрезов соответсвенно.
  2. Во второй строке n чисел (ограничения на сами числа - миллиард, т.е. бревна могут быть очень длинными) - длины n бревен

Примеры:

Ввод:

2 3

7 9

Вывод:

4

Что я понял:

  1. Сортируем массив по возрастанию и работаем с последним (самым большим бревном)

  2. Резать можно пополам, но это не всегда выгодно (иногда лучше на 3 и более частей)

  3. Из-за ограничения по времени 1 сек перебирать все возможные варианты не получится (числа могут быть огромными)

  4. Был вариант отрезать от последнего (самого длинного бревна) второе по величине (предпоследнее), но это не работает с очень большими числами (когда бревна 10 20 10000)

UPD: Условие


Источник

Ответы (2 шт):

Автор решения: MBo

Задача на бинарный поиск. Целевой параметр - длина конечного куска.

Для текущей длины l смотрим, сколько требуется разрезов, чтобы разделить все брёвна на части длиной l

Cuts[i] = Ceil(A[i] / l) - 1  //округление вверх

Если разрезов больше k - увеличиваем длину и т.д.

Условие остановки, видимо, подойдет такое - верхний предел бинарного поиска и нижний предел округляются вверх к одному целому

 while Ceil(l_lo) != Ceil(l_hi):
    l = (l_lo + l_hi) / 2
    считаем сумму Cuts[]

На Python

import random, math
n = 98765
k = 72389235368
a = [random.randrange(100000, 999999999) for _ in range(n)]
#print(a)
lo = 0
hi = max(a)
while math.ceil(lo)!= math.ceil(hi):
    l = (lo + hi) / 2
    cnt = sum([(math.ceil(x / l) - 1) for x in a])
    if cnt <= k:
        hi = l
    else:
        lo = l
print(math.ceil(l))

Пример для 7 9.

Начальная длина 9 - требуется 0 + 0 = 0 разрезов. Мало.
Длина (0+9)/2=4.5 - требуется 1 + 1 = 2 разреза. Опять мало.
Длина (0+4.5)/2 = 2.25 - требуется 2 + 3 = 5 разрезов. Много.
Длина (2.25 + 4.5)/2=3.375 - требуется 2 + 2 = 4 разреза. Много.
Длина (3.375 + 4.5)/2=3.9375 - требуется 1 + 2 = 3 разреза. Нормально.
Делаем ещё несколько итераций, пока не увидим, что верхний и нижний предел стали менее 4

→ Ссылка
Автор решения: Leonid

Добавляю решение на JS. Бинарный поиск максимальной длины при заданном количестве резов.

За минимальное значение принимается оптимальная длина отрезка, условно соединенного в одно целое, бревна.

Входящий массив фильтруется: остаются только бревна, которые больше этого минимума. Так сокращается работа на каждой итерации.

Максимальное значение рабочего диапазона - максимальная длина бревна из оставшегося набора.

Сужение диапазона происходит только за счет нахождения середины этого диапазона и назначения ее минимуму/максимуму. Поэтому устанавливается точность, которая достаточна для вычислений.

function findMaxLen(N,K,...A){
    let min = A.reduce((sum,item) => sum + item, 0)/(N+K); // Идеально минимальное значение длины
    let arr = A.filter(a => a > min);// Оставляем в рабочем массив только бОльшие min
    let max = arr.sort((a,b) => b - a)[0]; // Максимальная длина бревна
    let l = 0; // Текущая длина для каждой итерации, инициализирована нулем
    
    while(max - min > 0.001){ // 0.001 - предел точности схождения поиска
        l = (max + min)/2;
        let cutsNum = arr.reduce((sum, item) => sum + Math.ceil(item/l) - 1, 0); //Кол-во резов при этой длине
        if(cutsNum <= K){
            max = l; 
        } else {
            min = l;
        }
    }
    
    return Math.ceil(min);
    
}

console.log(findMaxLen(2,3,7,9));
console.log(findMaxLen(3,0,3,4,5));

Соглашаюсь с гениальностью MBo с проверкой на Math.ceil(max) != Math.ceil(min) в цикле.

Тогда поиск завершится сразу, как только любое значение текущего диапазона будет преобразовано в один и тот же результат.

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

Например, при findMaxLen(2,3,4,6) раскрой получается оптимальным и находится сразу - 2. Добавляю проверку для min = правильный ответ:

let cutsMin = arr.reduce((sum, item) => sum + Math.ceil(item/min) - 1, 0);
if(cutsMin == K) return Math.ceil(min);

Или findMaxLen(4,1,3,4,1000000000,1000000000), где недостаточно резов чтобы уменьшить максимальную длину бревна. То же при findMaxLen(3,0,3,4,5). Добавляю проверку для этого случая. То есть, если минимальное значение длины, которое будет округленно вверх до max - 1 уже не будет соответствовать количеству резов, то max - правильный ответ:

let cutsMax = arr.reduce((sum, item) => sum + Math.ceil(item/(Math.ceil(max) - 1)) - 1, 0);
if(cutsMax > K) return Math.ceil(max);

Если дальше следовать логике урезания циклов, то можно добавить проверку в тело цикла:

if(max - min <= 1){
    if(arr.reduce((sum, item) => sum + Math.ceil(item/Math.ceil(min)) - 1, 0) <= K){
        return Math.ceil(min);
    } else {
        return Math.ceil(max);
    }
}

Смысл в том, что на границе целого числа, например, min = 2, max = 2.1, (при правильном ответе 2) алгоритм будет сокращать диапазон до момента, пока не будет достигнут предел дробной части и max не будет преобразовано в 2. Однако на момент, когда разница между крайними значениями меньше или равнa 1, весь диапазон может быть преобразован только к двум ответам - Math.ceil(min) и Math.ceil(max). Тогда достаточно проверить min на соответствие кол-ву резов.

function findMaxLen(N,K,...A){
    let min = A.reduce((sum,item) => sum + item, 0)/(N+K); // Идеально минимальное значение длины
    let arr = A.filter(a => a > min);// Оставляем в рабочем массив только бОльшие min
    let max = arr.sort((a,b) => b - a)[0]; // Максимальная длина бревна
    let l = 0; // Текущая длина для каждой итерации, инициализирована нулем
    
    // Если кол-во резов при длине min равно K, то сразу возвращаем Math.ceil(min)
    let cutsMin = arr.reduce((sum, item) => sum + Math.ceil(item/min) - 1, 0);
    if(cutsMin == K) return Math.ceil(min);
    
    // Если минимальное значение, которое при округлении вверх будет меньше на 1,
    // не удовлетворяет условие, то возвращаем Math.ceil(max)
    let cutsMax = arr.reduce((sum, item) => sum + Math.ceil(item/(Math.ceil(max) - 1)) - 1, 0);
    if(cutsMax > K) return Math.ceil(max);
    
    console.log('Вошел в цикл');
    while(Math.ceil(max) != Math.ceil(min)){
        l = (max + min)/2;
        let cutsNum = arr.reduce((sum, item) => sum + Math.ceil(item/l) - 1, 0); //Кол-во резов при этой длине
        if(cutsNum <= K){
            max = l; 
        } else {
            min = l;
        }

        if(max - min <= 1){
            if(arr.reduce((sum, item) => sum + Math.ceil(item/Math.ceil(min)) - 1, 0) <= K){
                return Math.ceil(min);
            } else {
                return Math.ceil(max);
            }
        }
    }
    
    return Math.ceil(min);
    
}

console.log(findMaxLen(2,3,7,9));
console.log(findMaxLen(3,0,3,4,5));
console.log(findMaxLen(4,1,3,4,1000000000,1000000000));
console.log(findMaxLen(2,3,4,6));

Еще проще установить условие для самого цикла: while(max - min > 1), а проверять и выводить min или max за пределами цикла:

function findMaxLen(N,K,...A){
    let min = A.reduce((sum,item) => sum + item, 0)/(N+K); // Идеально минимальное значение длины
    let arr = A.filter(a => a > min);// Оставляем в рабочем массив только бОльшие min
    let max = arr.sort((a,b) => b - a)[0]; // Максимальная длина бревна
    let l = 0; // Текущая длина для каждой итерации, инициализирована нулем
    
    // Если кол-во резов при длине min равно K, то сразу возвращаем Math.ceil(min)
    let cutsMin = arr.reduce((sum, item) => sum + Math.ceil(item/min) - 1, 0);
    if(cutsMin == K) return Math.ceil(min);
    
    // Если минимальное значение, которое при округлении вверх будет меньше на 1,
    // не удовлетворяет условие, то возвращаем Math.ceil(max)
    let cutsMax = arr.reduce((sum, item) => sum + Math.ceil(item/(Math.ceil(max) - 1)) - 1, 0);
    if(cutsMax > K) return Math.ceil(max);

    while(max - min > 1){
        l = (max + min)/2;
        let cutsNum = arr.reduce((sum, item) => sum + Math.ceil(item/l) - 1, 0); //Кол-во резов при этой длине
        if(cutsNum <= K){
            max = l; 
        } else {
            min = l;
        }
    }
    
    if(arr.reduce((sum, item) => sum + Math.ceil(item/Math.ceil(min)) - 1, 0) <= K){
        return Math.ceil(min);
    } else {
        return Math.ceil(max);
    }   
}

console.log(findMaxLen(2,3,7,9));
console.log(findMaxLen(3,0,3,4,5));
console.log(findMaxLen(4,1,3,4,1000000000,1000000000));
console.log(findMaxLen(2,3,4,6));

→ Ссылка

licensed under cc by-sa 3.0 with attribution.