мы дали два массива 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).
Всего 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, но это не большая проблема.