минимизируя максимальный hundai, заменив его bmw

мы дали два массива H [] и B [] как размера n . H [i] обозначает количество автомобилей hundai (i) th человек. У меня есть автомобиль BMW, который я могу заменить хундай. B [i] содержит количество автомобилей hundai, эквивалентное 1 BMW (для каждого человека эквивалент может отличаться). Дано:

H[i]%B[i]=0;

Вопрос заключается в том, чтобы минимизировать max (H [i]) , заменив его BMW (обратите внимание, что у нас только м BMW). O (n) или O (nlogn).

algorithm data-structures

Всего 2 ответа

Идеи, вращающиеся вокруг minimizing .. the maximum of .. доступны с помощью двоичного поиска. Я ответил на вопрос по тем же строкам здесь: https://stackoverflow.com/a/52679263/10291310

Для вашего случая мы можем изменить алгоритм,

start = 0, end = 10^18 // Or your max `M` limit
while start <= end:
    bmw_used = 0 // Number of bmws used till now for this iteration
    mid = (start + end) / 2
    // Let's see if its possible to lower down all the hyndais such
    // that number of each hundai <= mid
    for i in range(0,N):
        if H[i] > mid:
            // Calculate the number of bmws required to bring H[i] <= mid
            bmw_required = ceil(1.0 * (H[i] - mid) / B[i])
            bmw_used += bmw_required
    // After iterating over the Hyndais
    if bmw_used > M:
        // We're exceeding the number of bmws, hence increase the number of huyndai
        start = mid + 1
    else:
        // We still have some more bmws left, so let's reduce more hyndais
        end = mid - 1

return start

Общая сложность выполнения решения - O (N * log (M)) . Ура!

псевдокод

for k = 1 to m
  max_i = 0
  for i = 1 to n-1
    if H[max_i] < H[i] then max_i = i
  if H[max_i] >= B[max_i] then H[max_i] -= B[max_i]
  else break

Общая сложность O (mn).
Если вы можете игнорировать m, это будет O (n).
Этот алгоритм может иметь некоторые ненужные циклы, когда есть одинаковые значения H, но это не большая проблема.