[TOC]
同學(xué)問(wèn)我一個(gè)字節(jié)跳動(dòng)的面試的算法問(wèn)題
昨晚我的一個(gè)同學(xué)問(wèn)了我下面這個(gè)問(wèn)題咖气，說(shuō)是字節(jié)跳動(dòng)面試的題目：
一根火柴能拆成兩份，然后放在原處挖滤。
拆了的 還可以再拆
最后保證非下降
問(wèn) 最少要拆幾次
比如 3 5 13 9 12 變成 3 5 6 7 9 12崩溪。1次就好了
我的第一感覺(jué)是這個(gè)或許應(yīng)該可以線(xiàn)性復(fù)雜度解決，很有可能是有貪心策略的斩松。
首先想到的是伶唯，應(yīng)該從后面開(kāi)始掃起，因?yàn)榍懊娴幕鸩癜麸@然不能超過(guò)后面的火柴棒的長(zhǎng)度惧盹。
然后我發(fā)現(xiàn)來(lái)可能需要解決一個(gè)問(wèn)題乳幸，如果前面的火柴棒比后面的長(zhǎng)瞪讼，那么怎么切分它合適？
一個(gè)自然的想法是要讓最短的小棒盡可能長(zhǎng)粹断，這樣對(duì)于前面的小棒而言上限就更大一些符欠。顯然長(zhǎng)度上限越大越好（至少上限大的不會(huì)比上限小的差）。
但是姿染，我發(fā)現(xiàn)需要考慮一個(gè)問(wèn)題背亥，雖然這樣有利于前面的小棒切分?jǐn)?shù)盡可能少秒际，但是對(duì)當(dāng)前的方案來(lái)講悬赏，是否存在一種劃分方案，它切分的出來(lái)的最短小棒雖然更短一些娄徊，但是對(duì)于前面的小棒的限制效果是一樣的（比如最短長(zhǎng)棒盡可能長(zhǎng)可以達(dá)到10 闽颇，而另一種切分方案最短小棒是8，而前面的小棒長(zhǎng)度是7寄锐，那么10和8對(duì)于7的限制效果是一樣的）兵多，但是切分出來(lái)的小棒數(shù)目更少。
稍微一想橄仆，直覺(jué)上可以看出不存在這種情況剩膘。因?yàn)槿绻疃绦“舾痰那懈罘桨福庇X(jué)上就是切分的比較零碎盆顾，那么切分成的小棒數(shù)就不應(yīng)該更少怠褐。當(dāng)然，這個(gè)直覺(jué)上是對(duì)的結(jié)論沒(méi)有那么顯然您宪。所以奈懒，我后面的分析去證明了這個(gè)結(jié)論，即盡可能切的數(shù)目小的情況下宪巨，最短小棒越長(zhǎng)磷杏， 切分出來(lái)的小棒數(shù)越少。
所以問(wèn)題就變成了捏卓，知道小棒原始長(zhǎng)度和小棒長(zhǎng)度上限极祸，讓切分成的最短小棒長(zhǎng)度盡可能長(zhǎng)，最短小棒可以是多長(zhǎng)怠晴，以及最少要切幾次贿肩。
于是就有了下面的子問(wèn)題A和子問(wèn)題B.
則稱(chēng)為
的一種整數(shù)劃分。
子問(wèn)題A(a,b)
輸入龄寞。問(wèn)在
的所有劃分中汰规，要求劃分中的最大數(shù)不超過(guò)
，最小數(shù)最大可以是多少物邑。
即求滿(mǎn)足下式最大的.
-
-
- 顯然
- 先劃分成k根a和一根r的小棒溜哮，之后滔金，我們只需要將
根a長(zhǎng)度的小棒每根截取
加到
這個(gè)小棒即可構(gòu)造出最小長(zhǎng)度為
的劃分方案。
- 即
- 顯然
-
令
,則
. 下為證明.
-
.
- 所以拆分的小棒不可能少于
根.
- 所以拆分的小棒不可能少于
- 假設(shè)劃分成
根小棒餐茵，最短的小棒
.
- 則
.
- 又
.
- 顯然矛盾。故不存在最小長(zhǎng)度大于
的方案述吸。
- 則
- 考慮劃分成
根小棒.
- 注意有
.
- 先
給
- 所以存在一種劃分方案最短長(zhǎng)度為
- 注意有
-
-
結(jié)論
返回.
子問(wèn)題B(a,b,n)
假設(shè)拆分可以使用的數(shù)限于 之間的正整數(shù)蝌矛，問(wèn)
可否實(shí)現(xiàn)整數(shù)劃分道批，以及劃分的根數(shù)最小可以是多少?
討論可以拆分的數(shù) 的情況:
也就是說(shuō),可由限于
之間的正整數(shù)拆分表示的數(shù)落在以下有限個(gè)區(qū)間內(nèi)：
另外，顯然入撒，假設(shè)長(zhǎng)度可以由上述規(guī)則進(jìn)行整數(shù)拆分表示隆豹，則，如果
,則
一定可以劃分成的小棒數(shù)一定不超過(guò)成
根茅逮。如果
則不但可以劃分成m根小棒璃赡，而且至少需要m根小棒才可以劃分。換句話(huà)說(shuō)可能存在多余m根小棒的劃分方案献雅，但是一定不存在小于m根的方案碉考，并且一定存在一種方案可以劃分成m根。
結(jié)論
若 可劃分挺身，劃分的最小根數(shù)d滿(mǎn)足
,即
.
返回是否可以劃分及.
回到原問(wèn)題
輸入數(shù)組.
算法
r=a[n] # 長(zhǎng)度上限
count = 0
for i = n downto 1
if a[i] <= r
r = a[i] # 更新長(zhǎng)度上限
continue
l = A(r) # 長(zhǎng)度下限
ok, d = B(l,r,a[i]-l) // 事實(shí)上ok肯定是true，因?yàn)殚L(zhǎng)度下限是由子問(wèn)題A求出來(lái)的瞒渠。
count += d
r = l # 更新長(zhǎng)度上限
print(count)
正確性說(shuō)明
長(zhǎng)度為 的小棒,劃分長(zhǎng)度上限為
, 記
. 則根據(jù)以上關(guān)于子問(wèn)題A良蒸、B的討論知道一定存在一種劃分方案
.
為了方便討論，不妨假設(shè)劃分方案中的數(shù)是不下降排列的伍玖，即.
假設(shè)存在一種劃分方案.
由子問(wèn)題A可知.
因?yàn)樽訂?wèn)題B是在限定了長(zhǎng)度上下限時(shí)嫩痰，求最小劃分根數(shù)。故有：
顯然與假設(shè)矛盾窍箍。
結(jié)論1
這就說(shuō)明劃分方案
既是最短的小棒盡可能長(zhǎng)的最佳方案串纺，又是劃分劃分小棒數(shù)盡可能少的最佳方案。
一方面椰棘，對(duì)于當(dāng)前小棒來(lái)講纺棺，劃分小棒數(shù)應(yīng)該盡可能小邪狞；
另一方面祷蝌，顯然劃分的最短小棒棒長(zhǎng)會(huì)作為前面的小棒的劃分上限，所以這個(gè)最短小棒越長(zhǎng)越好帆卓。
而結(jié)論1說(shuō)明我們的劃分方案在上面兩個(gè)方面努力的結(jié)果是一致的巨朦，所以我們可以采取算法所述的貪心措施米丘。
