algorithm - 通过用 bmw 替换它来最小化最大 hundai

Question

我们已经给出了两个大小为 n 的数组 H[ ] 和 B[ ]。H[i] 表示第(i) 人拥有的现代汽车数量。我有'' BMW 车，我可以用hundai 代替。B[i] 包含相当于 1 BMW 的 hundai 汽车数量(意味着每个人的等价性可能不同)。给定:

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

问题是通过用 BMW 替换它来最小化 ma​​x(H[i])(注意我们只有 m BMW)。需要 O(n) 或 O(nlogn) 的解决方案。

Answer 1

围绕最小化.. .. 的最大值 的想法可以使用二进制搜索 来解决我在这里回答了同样的问题: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))。干杯!