用宝马取代hundai，使其最小化

Question

我们给出了两个阵列H 和B ，它们的大小都是n。Hi是指(i)th人拥有的呼达汽车的数量。我有m‘宝马汽车，我可以用hundai代替它。Bi包含相当于1宝马(意味着每个人的当量可能不同)的呼达汽车数量。Given:

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

问题是最小化 max(Hi)，代之以宝马(请注意，我们只有m宝马)。需要O(n)或O(nlogn)解。

Answer 1

围绕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))。干杯!