0

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

Условие:

У вас есть 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: Условие

12
  • То есть, надо разрезать бревна так, чтобы максимальный кусок был минимальным? Зачем бы передавать миллиард бревен если вы работаете с одним? Скорее всего надо сделать бревна (куски бревен) максимально одинаковыми, усреднить. Тогда самый большой из оставшихся кусков будет минимально возможным по длине. Вывод 4 потому что 9 делим на 3 части по 3, а 7 пополам - по 3.5, которое округляется в бОльшую сторону - 4.
    – Leonid
    31 авг 2021 в 13:28
  • @Leonid не совсем правильно описал условие, бревен не миллиард, это ограничение на их длину, сейчас исправлю вопрос Саму задачу понял, не могу понять каким способом находить решение (как выбрать делить на 2, 3 или более частей самое большое бревно) Да, надо разрезать бревна так, чтобы самый большой кусок получился минимально возможным
    – Артём
    31 авг 2021 в 13:42
  • Приведите ссылку на задачу, почитаем в оригинале условия, а не ваш пересказ.
    – A K
    31 авг 2021 в 13:50
  • По-моему, задача сводится к следующему: найти минимальное t такое, что Sum(RoundUp(Ai / t - 1)) максимально, но не превышает K. Если я прав, то обычный поиск оптимума, делай хоть половинным делением... причём достаточно, чтобы верхнее и нижнее приближения имели равную целую часть.
    – Akina
    31 авг 2021 в 13:54
  • 1
    @user7860670 нужно разрезать бревна так, чтобы самый большой из оставшихся кусков (или целых бревен) был наименьшим. Если не резать, то оптимально минимальной длины не добиться. В первом случае 9 = 3 + 3 + 3 (2реза), 7 = 3.5 + 3.5 (1рез) - самый большой 3.5, округляем до 4. Во втором случае резов не производится и выводится тупо самое большое бревно.
    – Leonid
    31 авг 2021 в 14:06

2 ответа 2

8

Добавляю решение на 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));

13
  • Хотя округление до целого вообще странно в условиях, если оптимальная длина будет найдена в диапазоне +-0.0005 от целого числа ( а идеально как раз это целое число как при findMaxLen(2,3,4,6) -> 2), то что собственно отправлять на округление вверх? Min, Max, L? Или алгоритм должен все-таки работать только с целыми числами?
    – Leonid
    31 авг 2021 в 19:40
  • И задания странные "олимпиадные". Зачем вообще передавать число бревен, если передается n количество длин этих бревен. Задача про бревна, а формулировка какая-то технократическая - выведите одно число... Когда можно просто - закажите (сколотите) минимальный по длине контейнер для бревен, которые можно распилить не более K раз. И все))
    – Leonid
    31 авг 2021 в 19:49
  • Попробуйте ещё условие остановки, которое я дописал - max и min находятся в одном промежутке между последовательными целыми числами. Вдруг хитрые примеры придумают, в которых будет min 3.99999999, max 4.00000001, а решение 4.0000000001
    – MBo
    1 сен 2021 в 3:25
  • Эх, заплюсовал, Math.floor(item/l) сразу не заметив.. Для бревна 2 и длины 1 вернёт 2 реза
    – MBo
    1 сен 2021 в 3:38
  • Да я поменял на Math.ceil -1. А на счет 3.9999 - 4.0001 (в моем случае и этого достаточно) я и говорил. Изначально у меня не было проверки на минимальный разбег, просто (max != min), но я посчитал, что это не правильная эксплуатация программного округления сверхмалых чисел. Ведь в чистой математике дробить можно бесконечно. Хотя по условиям можно указать 0.5e-9?
    – Leonid
    1 сен 2021 в 5:09
7

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

Для текущей длины 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

10
  • А первая идеальная длина в качестве базового размера Sum(...A)/(N+K)? Для длины 3 в примере 9 и 7 надо сколько резов? Вроде 3 получится?
    – Leonid
    31 авг 2021 в 16:24
  • Первую длину можно взять Max(A), это особой роли не играет. Для данного примера нужно 4 разреза, я зря целочисленное деление (ведущее к округлению вниз) использовал
    – MBo
    31 авг 2021 в 16:30
  • Min(A)? Мы же увеличиваем длину... Все-таки мне кажется, что Sum(A)/(N+K) - идеально возможная минимальная длина, с нее и надо начинать. То есть, при 2,3,7,9 -> 16/5 -> 3. А так Max(A) = 9, Min(A) = 7. Понял, это же бинарный поиск....
    – Leonid
    31 авг 2021 в 16:39
  • @MBo спасибо большое за ответ, но у меня, к сожеланию, пока недостаточно опыта, чтобы понять как это реализовать по такому отрывку кода. Не могу разобраться откуда берется L, массивы A и Cuts. Я так понимаю что мы должны подобрать такое l, чтобы условие выполнилось, но тогда я не понимаю за что отвечает i Заранее прошу прощения, если слишком туплю
    – Артём
    31 авг 2021 в 16:40
  • @Leonid я видимо совсем не понял ваш подход к решению. Нам же надо найти не кол-во разрезов оптимальное, а длину конечных бревен
    – Артём
    31 авг 2021 в 16:49

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.