P
не пойму
Size: a a a
2020 June 18
И
сама задача описана довольно точно - minimize the sum of the elements in the final array
P
мм, да, согласен.
P
тогда как понимать пример?
.
Paul
но они начинают с 7
По их логике начали с минимального, дошли до максимального элемента в изначальном массиве
В примере k = 4
За три операции проход от минимального 7 до максимального 20
На последней операции выбрали максимальное и с ним произвели действия
В примере k = 4
За три операции проход от минимального 7 до максимального 20
На последней операции выбрали максимальное и с ним произвели действия
P
сек, я сейчас накидаю алгоритм, что мы тут с Иваном обсудили
И
Paul
тогда как понимать пример?
мне кажется просто решили не писать в правильном порядке что бы не слишком сильно раскрывать алгоритм
И
иначе по примеру можно было бы понять что каждый раз надо просто брать максмимум
В
Может все же минимальное количество элементов в конечном массиве?
P
оно не может уменьшиться
P
при бесконечном k массив будет состоять из единиц, но его длина будет как у входящего
В
А разве не надо каждую операцию выполнять с получившимися прежде цифрами?
P
там выполняется деление на 2 и ceil, любое i > 1 неизбежно становится единицей и потом сотается во всех итерациях
P
В общем, вот рабочий код:
def minSum(num, k)
k.times do
max = num.max
ind = num.index(max)
num.delete_at(ind)
num.insert(ind, (max / 2.0).ceil)
end
num.sum
end
p minSum([10 ,20, 7], 4)
P
засад здесь две: надо иметь ввиду, что деление Int дает целое чисо, поэтому нужно один из операндов привести к Float (я использовал запись
2.0) и второе — delete(max) просто, но не прокатит, сломает всю логику, когда в массиве будет больше одного элемента со значением maxИ
удалять вообще не обязательно можешь просто сделать num[ind] = new_value
P
кстати, да, можно и так
.
Иван
удалять вообще не обязательно можешь просто сделать num[ind] = new_value
По условию необходимо
P
по идее, должен быть верный результат и всё. если можно оптимизировать алгоритм, то это только в плюс
P
эх, кривое описание всё портит.