分而治之：计算经过的时间

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

bs:

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'然后重试，直到行数太大大.

此时，你的maximum是t，你的minimum是t/2。你再重复：

选择 t 作为 maximum 和 minimum
调用linesAt(t,...)获取行数
如果找到目标，停止。
如果行数太多，调整最大值：maximum = t
如果行数太少调整最小值：minimum = t

上述算法是一种二分搜索 - 每次迭代将搜索 space 分成两半。因此，它是分而治之的例子。

Answer 2

您正在尝试求解一个整数方程：

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

你可以去掉floor函数，求解n得到下界和上界，然后在这两个界之间搜索。

求解以下等式：

(n/7)*1+(n/8)*1+(n/10)*2 = 19
n=19/(1/7+1/8+2/10)

找到 n 后，m0 的值范围是 floor (m0 / 7) = floor (n/7)?

floor (n/7) * 7 <= m0 <= (ceiling (n/7) * 7) - 1

同理计算m1和m2

i在1到3之间取max(mi)为上界，min(mi)为下界。

此时进行二分查找可能有点矫枉过正。

分而治之：计算经过的时间

divide and conquer: computing the time elapsed

java

recursion

brute-force

floor

divide-and-conquer