字节跳动面试算法题一堆火柴棒长度的序列，切分成不下降的火柴棒长

2020-04-13 本文已影响0人稻云麦花

[TOC]

同学问我一个字节跳动的面试的算法问题

昨晚我的一个同学问了我下面这个问题，说是字节跳动面试的题目：

一根火柴能拆成两份，然后放在原处。
拆了的还可以再拆
最后保证非下降
问最少要拆几次
比如 3 5 13 9 12 变成 3 5 6 7 9 12。1次就好了

我的第一感觉是这个或许应该可以线性复杂度解决，很有可能是有贪心策略的。
首先想到的是，应该从后面开始扫起，因为前面的火柴棒显然不能超过后面的火柴棒的长度。

然后我发现来可能需要解决一个问题，如果前面的火柴棒比后面的长，那么怎么切分它合适？

一个自然的想法是要让最短的小棒尽可能长，这样对于前面的小棒而言上限就更大一些。显然长度上限越大越好（至少上限大的不会比上限小的差）。

但是，我发现需要考虑一个问题，虽然这样有利于前面的小棒切分数尽可能少，但是对当前的方案来讲，是否存在一种划分方案，它切分的出来的最短小棒虽然更短一些，但是对于前面的小棒的限制效果是一样的（比如最短长棒尽可能长可以达到10 ，而另一种切分方案最短小棒是8，而前面的小棒长度是7，那么10和8对于7的限制效果是一样的），但是切分出来的小棒数目更少。

稍微一想，直觉上可以看出不存在这种情况。因为如果最短小棒更短的切割方案，直觉上就是切分的比较零碎，那么切分成的小棒数就不应该更少。当然，这个直觉上是对的结论没有那么显然。所以，我后面的分析去证明了这个结论，即尽可能切的数目小的情况下，最短小棒越长，切分出来的小棒数越少。

所以问题就变成了，知道小棒原始长度和小棒长度上限，让切分成的最短小棒长度尽可能长，最短小棒可以是多长，以及最少要切几次。

于是就有了下面的子问题A和子问题B.

$n=\sum_{i}^{k}{a_i} \quad (a_i \in N^{+})$
则称 $a_1,a_2,\dots,a_k$ 为 $n$ 的一种整数划分。

子问题A(a,b)

输入 $a,b(b>a)$ 。问在 $b$ 的所有划分中，要求划分中的最大数不超过 $a$ ，最小数最大可以是多少。

即求满足下式最大的 $c$ .
$b=\sum_{i}^{k}{b_i} \quad \& \quad \max_{i}^{k}\{b_i\} \le a \quad \& \quad \min_{i}^{k}\{b_i\}=c$

$b=ka \; \Rightarrow c=a.$
1. 1. 显然 $c=a-1.$
  2. 先划分成k根a和一根r的小棒，之后，我们只需要将 $a-1-r \le a-2 \le k$ 根a长度的小棒每根截取 $1$ 加到 $r$ 这个小棒即可构造出最小长度为 $c=a-1$ 的划分方案。
  3. 即 $a \nmid b \wedge b\ge (a-1)^2 \Rightarrow c=a-1.$
2. 令,则. 下为证明.
  1. .
    1. 所以拆分的小棒不可能少于 $k$ 根.
  2. 假设划分成根小棒，最短的小棒.
    1. 则 $b \ge pc_1 \ge (k+1)(c_0+1)$ .
    2. 又 $b=c_0 \cdot (k+1)+r_0 (0 \le r_0 < k+1) \rightarrow b < c_0 \cdot (k+1)+ (k+1)=(c_0+1)(k+1)$ .
    3. 显然矛盾。故不存在最小长度大于 $c_0$ 的方案。
  3. 考虑划分成根小棒.
    1. 注意有 $b=c_0 \cdot (k+1)+r_0 (0 \le r_0 < k+1)$ .
    2. 先 $k+1$ 根 $c_0$ 的小棒，然后剩余的 $r_0$ 给 $r_0$ 根小棒各自加1即可。
    3. 所以存在一种划分方案最短长度为 $c_0$ .

结论

返回 $c$ .

子问题B(a,b,n)

假设拆分可以使用的数限于 $[a,b]$ 之间的正整数，问 $n$ 可否实现整数划分，以及划分的根数最小可以是多少?

讨论可以拆分的数 $n$ 的情况:
$\left[a,b \right] \\ \left[2a,2b \right] \\ \left[3a,3b \right] \\ \dots \\$

$kb \ge (k+1)a \quad(k \in N^{+}) \;\Rightarrow\; k \ge \lceil \frac{a}{b-a} \rceil = (b-1)\; div \; (b-a)$

也就是说 $k=(b-1)\; div \; (b-a)$ ,可由限于 $[a,b]$ 之间的正整数拆分表示的数落在以下有限个区间内：
$\left[a,b \right] \\ \left[2a,2b \right] \\ \left[3a,3b \right] \\ \dots \\ \left[(k-1)a,(k-1)b \right] \\ \left[ka,+\infty \right] \\$

另外，显然，假设长度 $n$ 可以由上述规则进行整数拆分表示，则，如果 $n<=mb$ ,则 $n$ 一定可以划分成的小棒数一定不超过成 $m$ 根。如果 $(m-1)b<n<=mb$ 则不但可以划分成m根小棒，而且至少需要m根小棒才可以划分。换句话说可能存在多余m根小棒的划分方案，但是一定不存在小于m根的方案，并且一定存在一种方案可以划分成m根。

结论

若 $n$ 可划分，划分的最小根数d满足 $(d-1)\cdot b < n \le d \cdot b$ ,即 $d=\lceil \frac{n}{b} \rceil = (n+b-1) \; div \; b$ .

返回是否可以划分及 $d$ .

回到原问题

输入数组 $a[1..n]$ .

算法

r=a[n] # 长度上限
count = 0
for i = n downto 1
    if a[i] <= r
        r = a[i] # 更新长度上限
        continue
    l = A(r) # 长度下限
    ok, d = B(l,r,a[i]-l) // 事实上ok肯定是true，因为长度下限是由子问题A求出来的。
    count += d
    r = l # 更新长度上限
print(count)