java - 分而治之 : computing the time elapsed

Question

我必须在大学做一个小作业:

我有一台运行“n”个独立服务的服务器。过去所有这些服务都是同时启动的。每个服务“i”都会在一定时间“s[i]”(以秒为单位)后将“b[i]”行写入服务器上的日志文件。输入由“l”日志文件行数和“n”服务数组成。然后，我们在接下来的“n”行中为每个服务 i 提供:“s[i]”是前面提到的周期，“b[i]”是服务写入日志文件的行数。

我必须根据日志文件中的行数计算出程序在多久之前(以秒为单位)开始运行。示例:

input:  
19 3 
7 1
8 1
10 2

Output: 
42

我必须使用分而治之的方法，但我什至不知道如何将其分解为子问题。另外我必须使用这个函数，其中 ss 是服务周期的数组，bs 是每个服务写入日志文件的行数:

long linesAt(int t, int[] ss, int[] bs) {
  long out = 0;
  for (int i = 0; i < ss.length; i++) {
     // floor operation
     out += bs[i] * (long)(t/ss[i]);
  }
  return out;

ss 和 bs 基本上是输入数组，如果我们举个例子，它们将如下所示，其中上面的行是数组的索引:

SS:

0 1 2
7 8 10

废话:

0 1 2
1 1 2

很容易看出输出应该是42

 linesAt(42) = floor(42/7)*1+floor(42/8)*1+floor(42/10)*2 = 19

现在我必须编写一个函数

int solve(long l, int[] ss, int[] bs)

我已经用蛮力写了一些伪代码，但我不知道如何用分而治之的范式来解决这个问题，我的伪代码如下所示:

Solve(l, ss, bs)
  out = 0
  t = 0
  while (out != l)
    out = linesAt(t, ss, bs)
    t++
  end while
  return t

我想我必须以某种方式分割l，以便计算较小长度的时间。但我真的不明白怎么做，因为当你看到这个时，它似乎不可能:

t           out
0..6        0
7           1
8           2
9           2
10          4
11..13      4
14          5
15          5
16          6
17..19      6
20          8
...
40          18
42          19

尚塔尔。

Answer 1

听起来经典的二分搜索就符合要求，需要先一步来获得合适的最大值。您首先估计时间“t”(例如 100)，然后调用 linesAt 来获取该 t 的行数。如果返回的值太小(即小于l)，则将“t”加倍并重试，直到行数太大。

此时，您的最大值为t，您的最小值为t/2。然后你反复:

• 选择t作为最大值和最小值之间的中间点
• 调用linesAt(t,...)获取行数
• 如果您找到了目标，请停止。
• 如果行数过多，请调整最大值:maximum = t
• 如果行数太少，请调整最小值:minimum = t

上面的算法是二分搜索 - 它在每次迭代时将搜索空间分成两半。因此，这是一个分而治之的例子。