主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開始且長(zhǎng)度為 n 的整數(shù)陣列 stations，其中 stations[i] 代表著第 i 座城市裡的發(fā)電廠數(shù)量。
每一座發(fā)電廠可以提供電力給固定範(fàn)圍中的每一座城市。換句話說(shuō)，如果範(fàn)圍為 r，則一座位於城市 i 的發(fā)電廠可以提供電力給所有的城市 j 滿足 |i - j| ≦ r 且 0 ≦ i 、 j ≦ n - 1。
注意到 |x| 代表著絕對(duì)值。例如說(shuō)，|7 - 5| = 2 而 |3 - 10| = 7。
一座城市的電力為所有提供它電力的發(fā)電廠之電力總量。
政府批準(zhǔn)了再多興建 k 座發(fā)電廠，每一個(gè)可以蓋在任何一座城市裡，而且覆蓋半徑與先前存在的發(fā)電廠一致。
給定兩整數(shù) r 和 k，在額外的發(fā)電廠以最佳策略建造的情況下，回傳最小電力的城市之電力值最大可以為何。
注意到你可以在多座城市蓋這 k 座發(fā)電廠。
限制：
n == stations.length
1 ≦ n ≦ 10 ^ 5
0 ≦ stations[i] ≦ 10 ^ 5
0 ≦ r ≦ n - 1
0 ≦ k ≦ 10 ^ 9
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： stations = [1,2,4,5,0], r = 1, k = 2
輸出： 5
解釋：
一個(gè)最佳的方式來(lái)兩座新的發(fā)電廠興建在城市 1 裡。
所以 stations 將變成 [1,4,4,5,0]。
城市 0 從發(fā)電廠的供電為 1 + 4 = 5。
城市 1 從發(fā)電廠的供電為 1 + 4 + 4 = 9。
城市 2 從發(fā)電廠的供電為 4 + 4 + 5 = 13。
城市 3 從發(fā)電廠的供電為 5 + 4 = 9。
城市 4 從發(fā)電廠的供電為 5 + 0 = 5。
所以最小電力的城市之電力值為 5。
由於它不可獳得到更大的電力值，我們回傳 5。
範(fàn)例 2：
輸入： stations = [4,4,4,4], r = 0, k = 3
輸出： 4
解釋：
可以證明我們無(wú)法讓最小電力的城市之電力值大於 4。
解題思維：
又是一題可以對(duì)答案本身進(jìn)行二分搜尋法（Binary Search）的題目，如這題。
而要檢查當(dāng)前猜的值 M 太大或太小，則可以採(cǎi)取類似這題的方式——也就是當(dāng)現(xiàn)在看到的城市（假設(shè)是由左至右掃過(guò)）的電力不足 M 時(shí)，則需要興建新的發(fā)電廠。而為了可以覆蓋「後面的」城市（因?yàn)榭梢缘浆F(xiàn)在這座城市表示前面已經(jīng)處理好了），因此這個(gè)發(fā)電廠要盡量往後面的城市蓋。
如果整個(gè)過(guò)程加上現(xiàn)在的城市需求已經(jīng)蓋超過(guò) k 座發(fā)電廠。則代表一開始猜的 M 值太大了，要猜小一點(diǎn)；反之，如果全部掃完之後蓋的發(fā)電廠 ≦ k 個(gè)，則代表我們有機(jī)會(huì)可以猜得比 M 還大。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
