Добавляю решение на 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));
t
такое, чтоSum(RoundUp(Ai / t - 1))
максимально, но не превышаетK
. Если я прав, то обычный поиск оптимума, делай хоть половинным делением... причём достаточно, чтобы верхнее и нижнее приближения имели равную целую часть.