algorithm - 求从可以访问 B 包的 A 机器收集 C 礼物所需的最短时间？

Question

下周我有一个面试，我正在练习同样的问题。我遇到了这个问题，你能帮我解决一下吗？

There are A gift vending machines and you have B pouches to collect the gifts in. Each gift vending machine has unlimited gifts.

Each machine starts dropping the gift at time Si second and keeps dropping a gift every Ii seconds. You can arrange the pouches in any way you like but once they are set below one machine, you cannot move it to another machine. You need to collect a minimum of C gifts in minimum time.

Input

The first line contains the integers A, B, C.

The second line contains integers, Si. ( separated with a space), I goes from 1 to A.

The third line contains integers Ii ( separated with a space), I goes from 1 to A.

Output

An integer which gives the minimum time calculated.

我认为这种方法效率很低。我认为我们可以让基数等于 B 的所有子集，然后选择给出最短时间的子集。

这种方法似乎是蛮力，所以我正在寻找另一种替代方法。

谁能帮我解决一下吗？

Answer 1

首先写一个函数

int max_num_gifts(A,B,t,S[],l[])

它计算在 t 时间内您可以使用 B 包收集的最大礼物数量。这可以在 O(A) 时间内完成:给定 S[] 和 l[] 机器 A 的礼物数量[i] 掉落是 (t-S[i])/l[i]+1。然后获得掉落礼物最多的顶级 B 机器。参见 How to find the kth largest element in an unsorted array of length n in O(n)?关于如何在 O(n) 时间内进行选择。

然后你可以循环 t=1,2,... 直到 max_num_gifts >= C。或者更好的是，您可以使用二进制搜索来查找这样的 t:从 t=1 开始，然后检查 t=2，t=4, t=8 等直到你得到一个太大的数字，然后二进制搜索所需的 t。

整体时间复杂度应该是O(A* lg(T_min))。