У вас есть палочек произвольной длины, не обязательно интегральных.
Отрезая несколько палочек (один разрез режет одну палку, но мы можем резать так часто, как мы хотим), вы хотите получить палочек, которые бы:
- Все эти палочек имеют одинаковую длину;
- Все палок, по крайней мере, такие же, как и все остальные палочки.
Обратите внимание, что мы получаем палочек после выполнения надрезов.C
Какой алгоритм вы бы использовали, чтобы количество необходимых сокращений было минимальным? И что это за номер?
В качестве примера возьмем и любой . Можно использовать следующий алгоритм:n ≥ 2
- палочки в порядке убывания длины так, чтобы .
- Если то вырежьте палку № 1 на две равные части. Теперь есть две палки длиной , которые по крайней мере равны остальным палкам .л 1 / 2 2 ... п
- В противном случае ( ) разрезаем палку № 1 до двух неравных кусков размеров и . Теперь есть две палки длиной , которая длиннее, чем а остальные палочки .L 2 L 1 - L 2 L 2 L 1 - L 2 3 … n
В обоих случаях достаточно одного разреза.
Я попытался обобщить это для больших , но, похоже, нужно рассмотреть много случаев. Можете ли вы найти элегантное решение?
источник
Как подсказывает @randomA, мы будем действовать в два этапа: сначала мы найдем набор палочек, которые будут разрезаны, а затем сведем к минимуму количество разрезов.
Как и в особом случае в вопросе, мы сортируем / палочки так, чтобы . Это занимает время.L1≥L2≥⋯≥Ln O(nlogn)
Как указал @ user1990169, нам никогда не придется вырезать кусок, который .i≥k
На первом этапе мы используем бинарный поиск, чтобы найти число , , так что стики можно разрезать как минимум на кусков размера (плюс несколько меньших кусочков) , но палочки нельзя разрезать на кусков размером . Это займет времени.s 1≤s≤k 1,…,s k Ls 1,…,s−1 k Ls−1 O(klogk)
Если , это значение является оптимальным размером, и мы можем пропустить второй этап.Ls−1=Ls
В противном случае мы знаем, что оптимальный размер удовлетворяет а если то получается в результате разрезания хотя бы одной из палочек на куски одинакового размера. Фаза два будет определять :o Ls−1>o≥Ls o>Ls o o
Для каждого стержня , , определите набор подходящих размеров следующим образом: Если разрезание на куски размером превращает стержень в куски (включая более короткий, если он есть), то кандидаты на это stick - это все значения , где и . (См . Ответ @ user1990169, почему это единственные размеры кандидатов.)i 1≤i≤s Ls ri Lij j≤ri Lij<Ls−1
Поддерживать для каждого размера кандидата, как часто это происходило. Используя сбалансированное дерево поиска, это можно сделать в , поскольку общее количество размеров кандидатов ограничено .O(klogk) ∑iri≤2k
Теперь размер кандидата, который встречается чаще всего и приводит к правильному сокращению, является тем, который дает нам оптимальное решение. Кроме того, если какой-либо размер кандидата приводит к правильному резанию, любой меньший размер также приведет к правильному резанию.
Таким образом, мы снова можем использовать бинарный поиск, чтобы найти наибольшую длину кандидата, которая приводит к действительному сокращению в . Затем мы перебираем набор длин кандидатов до этого порога и находим тот, у которого наибольшее множество среди них в .O(klogk) O(k)
В итоге мы получаем время выполнения в или , если мы игнорируем (или не должны делать) начальную сортировку.O(nlogn) O(klogk)
источник
После того, как вы заказали палочки в порядке убывания их длины, тогда палка будет обрезана, только если все палки были обрезаны.Li L1,L2,...Li−1
Теперь, поскольку , мы не будем делать разрез на палках далее, поскольку у нас всегда может быть палочек длиной .k<n Lk k Lk
Таким образом, теперь вместо мы имеем дело только с стиками (возможно, добавляя стик в целом), а максимальное количество разрезов, которое потребуется в худшем случае .n k−1 k =k−1
Кроме того, если оптимальное количество порезов , то среди этих палочек должен быть по крайней мере один набор палочек, который должен быть взят целиком из 1 оригинальной палочки<k−1 k−1 (либо по частям, либо по 1 штуке). ни одна часть этой оригинальной флешки не должна быть оставлена «неиспользованной». Это связано с тем, что по принципу голубиного отверстия должен быть как минимум 1 разрез, который должен производить более 1 действующей палки.
Затем вы можете провести два вложенных цикла (оба до ). Внешний цикл должен обозначать номер стержня , все части которого должны быть взяты, а внутренний цикл должен обозначать количество частей изготовленных из этого стержня. Для каждого размера проверьте, можете ли вы получить выполнимые k палок, последовательно разрезая палки и, если можете, то обновите минимальные требуемые порезы, если текущий требуемый номер меньше.k i j
Lij L1
Общая сложность вышеупомянутого алгоритмаO(nlog(n)+k3)
источник
Идея высокого уровня - бинарный поиск.
Размер каждой из запрошенных k палочек будет, по крайней мере, наименьшей палкой и максимум самой большой. Поэтому мы продолжаем использовать бинарный поиск по размеру средней палки, посмотрим, какое число мы можем получить, если это больше заданного то мы знаем, что нам нужно выбрать новый эталонный размер кандидата. Таким образом, мы переходим к большему или меньшему, используя новый эталонный стик. Мы останавливаемся, когда меньше, чемk′ k′ k k′ k
Как только мы нашли соответствующий эталонный стержень, возникает угловой случай, когда нам нужно будет еще больше уточнить размер. Мы можем отсортировать все нарезанные палочки по количеству надрезов на них и размеру палочки. Выберите тот с наименьшим количеством сокращений и наименьшего размера. Уменьшите количество порезов на этой палочке на 1 и сделайте все вспомогательные палочки такого же размера. Это будет новый эталонный размер, проверьте, может ли этот новый размер привести к приемлемому . Признаюсь, я не знаю, как ограничить время выполнения в этом случае.k′
Надеюсь, я смогу увидеть что-то полезное из других ответов.
источник