Найдите минимально возможную высоту самой высокой башни - PullRequest
Новая
       34

Найдите минимально возможную высоту самой высокой башни

0 голосов
/ 06 октября 2018

У меня есть башни с высотой H = h1, h2, h3 ... и у меня есть режущий станок, который режет только каждую башню с определенной длиной A = a1, a2, a3 .. и у меня есть m срезов, чтобы найти минимумвозможная высота самой высокой башни.

для экс. H = 1, 4, 9, 16, 25 и A = 1,2,3,4,5

m = 3 (только3 разреза)

минимально возможная высота равна 15, так как после разрезов массив выглядит как H = 1,4,9,12,15 (после применения 0, 0, 0, 1, 2 разрезов соответственно на башнях)

То, что я пытался: я распознал это как жадную проблему (поправьте меня, если я ошибаюсь), и я попытался отсортировать массив H и простым способом сначала попытался сократить максимальную высоту, чтобы она больше не оставаласьмаксимум, а затем нашли новый максимум и снова применили те же шаги, это правильно, но это слишком наивно и требует большого количества времени для больших значений?

Время, необходимое для шагов: поиск максимального элемента каждый раз O (N) исортировка также не возможна (каждый раз).

Ограничения для n до 10 ^5 и m около 10 ^ 18.

Есть ли лучший подход?Веди меня !!

1 Ответ

0 голосов
/ 06 октября 2018

Вопросы вида minimum .. of the maximum .. обычно доступны по идее двоичного поиска .Мы можем сформулировать решение O (N * log (M)) для данного вопроса, применив бинарный поиск по метрике для оптимизации, то есть minimum possible height of the highest tower.Совместное использование псевдокода для того же самого: 

start = 0, end = 10^18
while start < end:
    cuts_used = 0 // Number of cuts used till now
    mid = (start + end) / 2
    // Let's see if its possible to trim down all the towers such
    // that height of each tower <= mid
    for i in range(0,N):
        if H[i] > mid:
            // Calculate the number of cuts required to bring H[i]<= mid
            cuts_required = ceil(1.0 * (H[i] - mid) / A[i])
            cuts_used += cuts_required
    // After iterating over the towers
    if cuts_used > M:
        // We're exceeding the number of cuts, hence increase the tower height
        start = mid + 1
    else:
        // We still have some more cuts left, so let's cut more
        end = mid - 1

return start

start должно быть нашим оптимальным ответом, поскольку наше условие определяется как while start < end.Рассмотрим случай, когда наш диапазон: start = 1 и end = 2. Середина для данного случая равна [(1 + 2) / 2] = 1.

  • Now If 1 действительно является нашим оптимальным ответом, тогда cuts_used, когда mid = 1 будет <= M, и, следовательно, наш логарифм переместится с конца на середину - 1, то есть 0. Следовательно, диапазон будет start = 1, end = 0, и мы 'Перестану зацикливаться.Очевидно, <code>start будет нашим решением.

  • Теперь для другого случая, когда 2 является решением, cuts_used для mid = 1 будет> M, и, следовательно, наш алгоритм переместится с начала на mid + 1, и диапазон станетstart = 2 и end = 2 - что заставляет нас прекратить зацикливание.

В любом из случаев видно, что start должно быть нашим оптимальным решением.

Также обратите внимание, что для вычисления ceil((H[i] - mid) / A[i]) мы не должны выполнять целочисленное деление, поскольку мы потеряем число с плавающей запятой и, следовательно, ceil не будет работать так, как задумано.Следовательно, ceil(1.0 * (H[i] - mid) / A[i]) следует учитывать, чтобы привести результат к плавающему входу для ceil.

...