字節(jié)跳動面試算法題 一堆火柴棒長度的序列，切分成不下降的火柴棒長度序列，要求切割長度最小 2020-04-13

[TOC]

同學(xué)問我一個字節(jié)跳動的面試的算法問題

昨晚我的一個同學(xué)問了我下面這個問題，說是字節(jié)跳動面試的題目：

一根火柴能拆成兩份，然后放在原處。
拆了的 還可以再拆
最后保證非下降
問 最少要拆幾次
比如 3 5 13 9 12 變成 3 5 6 7 9 12。1次就好了

我的第一感覺是這個或許應(yīng)該可以線性復(fù)雜度解決，很有可能是有貪心策略的。
首先想到的是，應(yīng)該從后面開始掃起，因為前面的火柴棒顯然不能超過后面的火柴棒的長度。

然后我發(fā)現(xiàn)來可能需要解決一個問題，如果前面的火柴棒比后面的長，那么怎么切分它合適？

一個自然的想法是要讓最短的小棒盡可能長，這樣對于前面的小棒而言上限就更大一些。顯然長度上限越大越好（至少上限大的不會比上限小的差）。

但是，我發(fā)現(xiàn)需要考慮一個問題，雖然這樣有利于前面的小棒切分?jǐn)?shù)盡可能少，但是對當(dāng)前的方案來講，是否存在一種劃分方案，它切分的出來的最短小棒雖然更短一些，但是對于前面的小棒的限制效果是一樣的（比如最短長棒盡可能長可以達到10 ，而另一種切分方案最短小棒是8，而前面的小棒長度是7，那么10和8對于7的限制效果是一樣的），但是切分出來的小棒數(shù)目更少。

稍微一想，直覺上可以看出不存在這種情況。因為如果最短小棒更短的切割方案，直覺上就是切分的比較零碎，那么切分成的小棒數(shù)就不應(yīng)該更少。當(dāng)然，這個直覺上是對的結(jié)論沒有那么顯然。所以，我后面的分析去證明了這個結(jié)論，即盡可能切的數(shù)目小的情況下，最短小棒越長， 切分出來的小棒數(shù)越少。

所以問題就變成了，知道小棒原始長度和小棒長度上限，讓切分成的最短小棒長度盡可能長，最短小棒可以是多長，以及最少要切幾次。

于是就有了下面的子問題A和子問題B.

n=\sum_{i}^{k}{a_i} \quad (a_i \in N^{+})
則稱a_1,a_2,\dots,a_k為n的一種整數(shù)劃分。

子問題A(a,b)

輸入a,b(b>a)。問在b的所有劃分中，要求劃分中的最大數(shù)不超過a，最小數(shù)最大可以是多少。

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

  1. b=ka \; \Rightarrow c=a.
  2. b=ka+r \; (1 \le r \ge a-1)
    1. k \ge (a-2).
      1. 顯然c=a-1.
      2. 先劃分成k根a和一根r的小棒，之后，我們只需要將a-1-r \le a-2 \le k根a長度的小棒每根截取1加到r這個小棒即可構(gòu)造出最小長度為c=a-1 的劃分方案。
      3. 即a \nmid b \wedge b\ge (a-1)^2 \Rightarrow c=a-1.
    2. k < (a-2). 令c_0=\lfloor \frac{k+1} \rfloor = b \; div \; (k+1),則c=c_0. 下為證明.
      1. \because b > ka.
        1. 所以拆分的小棒不可能少于k 根.
      2. 假設(shè)劃分成 p(p > k) 根小棒，最短的小棒c_1 > c_0.
        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. 考慮劃分成k+1 根小棒.
        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.

結(jié)論

返回c.

子問題B(a,b,n)

假設(shè)拆分可以使用的數(shù)限于[a,b] 之間的正整數(shù)，問n 可否實現(xiàn)整數(shù)劃分，以及劃分的根數(shù)最小可以是多少?

討論可以拆分的數(shù) 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] 之間的正整數(shù)拆分表示的數(shù)落在以下有限個區(qū)間內(nèi)：
\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] \\

另外，顯然，假設(shè)長度n可以由上述規(guī)則進行整數(shù)拆分表示，則，如果n<=mb,則n一定可以劃分成的小棒數(shù)一定不超過成m根。如果(m-1)b<n<=mb則不但可以劃分成m根小棒，而且至少需要m根小棒才可以劃分。換句話說可能存在多余m根小棒的劃分方案，但是一定不存在小于m根的方案，并且一定存在一種方案可以劃分成m根。

結(jié)論

若 n 可劃分，劃分的最小根數(shù)d滿足(d-1)\cdot b < n \le d \cdot b,即 d=\lceil \frac{n} \rceil = (n+b-1) \; div \; b.

返回是否可以劃分及d.

回到原問題

輸入數(shù)組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)

正確性說明

長度為 n 的小棒,劃分長度上限為r, 記l = A(n), d = 1 + B(l,r,n-l). 則根據(jù)以上關(guān)于子問題A、B的討論知道一定存在一種劃分方案b_1,b_2,\dots,b_u0z1t8os \quad (b_1 = l \wedge b_i \ge l).

為了方便討論，不妨假設(shè)劃分方案中的數(shù)是不下降排列的，即\forall i(i<n) \Rightarrow b_i \le b_{i+1}.

假設(shè)存在一種劃分方案c_1,c_2,\dots,c_m (m < d).

由子問題A可知c_1 \le b_1.

因為子問題B是在限定了長度上下限時，求最小劃分根數(shù)。故有：

m-1 \ge B(c_1,r,n-c_1) = \lceil \frac{n-c_1}{r} \rceil \ge \lceil \frac{n-b_1}{r} \rceil = B(b_1,r,n-b_1) = d-1$. 即$m \ge d

顯然與假設(shè)m<d矛盾。

結(jié)論1

這就說明劃分方案
b_1,b_2,\dots,b_u0z1t8os \quad (b_1 = l \wedge b_i \ge l)
既是最短的小棒盡可能長的最佳方案，又是劃分劃分小棒數(shù)盡可能少的最佳方案。

  1. 一方面，對于當(dāng)前小棒來講，劃分小棒數(shù)應(yīng)該盡可能小；

  2. 另一方面，顯然劃分的最短小棒棒長會作為前面的小棒的劃分上限，所以這個最短小棒越長越好。

而結(jié)論1說明我們的劃分方案在上面兩個方面努力的結(jié)果是一致的，所以我們可以采取算法所述的貪心措施。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容