這題有一個很單純的策略：每次找到最左邊需要翻面的煎餅，並將鍋鏟的最左側貼在他身上後翻面。

• 這是因為對於最左邊那個煎餅，也只有一種翻法可以翻到他，在處理好最左邊的煎餅後，就可以把最左邊的煎餅遮住當作沒看到。

不過此時有個新手會不小心忽略的問題：假設 $n$ 是字串的長度，整個鐵盤可能會需要翻到 $O(n-k)$ 次，如果 $k=\frac{n}{2}$，每次翻面又需要花 $O(k)$ 的時間，會直接讓時間複雜度大至 $\Theta(n^2)$！

以往要加速貪心的過程，似乎只需要排個序就完成了，但這在這題似乎行不通。

不妨仔細想像我們執行策略的過程，假設我們就正常的從左邊一路翻過來好了，當我們看到第 $i$ 個煎餅時，其實我們會在乎的是

• 他左邊的 $k-1$ 種操作被執行的總次數。

也就是說，對於他左邊的 $k-1$ 種位置，如果我們有試圖用鍋鏟將其貼在最左邊翻一次的話，這個煎餅就會跟著被翻一次，而這個次數的奇偶性、和這個煎餅的初始狀態其實就決定了當前這個煎餅的狀態！

另一方面來說，對於一次翻面操作，可以想像他就是一口氣讓連續的 $k$ 個煎餅身上被翻動的次數 $+1$，此時我們可能會需要能快速支援

• 對一個區間加上 $1$。

看到這樣的操作有想起什麼嗎？沒錯，就是我們在基礎演算法 / 前綴和與差分學過的差分！

如果仔細想一遍當初講解過的區間加值問題，就會發現因為我們的加值操作剛好是從左到右的，所以我們其實可以邊加、邊把最後的序列還原，這也就能同時幫助我們在 $O(1)$ 時間加值、$O(1)$ 時間得到當前煎餅的狀態。

因此，透過結合我們先前學過的知識，我們便成功加速了這個貪心策略到 $O(n)$ 時間。

讀者可以稍微模擬一些狀況，找找看最佳的「加法」順序到底是多少。

一個最直覺的想法便是找出最小的兩個數字將他們相加，而加完之後由於他們會形成新的數字，就當成規模少一的問題不斷做下去就行了。

也就是說，我們的貪心策略便是：不斷找出最小的兩個數字相加，直到剩下一個數字為止。

這個策略為什麼是正確的呢？他的證明其實有些複雜，直覺上可以想成是在計算加法的過程中，會希望盡量大的數字被加盡量少次，所以先處理較小的數字總是比較好。如果想看更嚴謹的證明的話，可以自行展開以下證明。

既然我們相信我們的貪心策略是正確的，那就是該來優化其時間複雜度的時間了。很明顯的，因為每次都要找到最小的兩個數字，加法又需要執行 $N-1$ 次，所以需要的總時間會是 $O(N^2)$ 的，肯定會超時。

不過，如果我們好好的把這個過程想成一個資料結構問題，會發現其實我們需要支援的是以下操作：

• 支援從資料結構中拿出最小值。
• 支援加入一個新的數字進入資料結構。

沒錯，我們的每一次加法其實就是「拿最小值」、「拿最小值」、「加入數字」三個上述資料結構的操作。而看著上述的敘述，想必讀者應該也發現了，這正是我們的 priority queue 能在 $O(\log N)$ 時間內辦到的！

綜上所述，我們便能在 $O(N\log N)$ 的時間內通過這題。如果讀者忘記 priority queue 怎麼使用，可以到基礎資料結構 / Heap 複習。

注意到我們可以先把數字重新換個順序，讓目標的排列恰好是 $1\sim n$。因此接下來我們就不失一般性的假設目標排列是 $1\sim n$。

這題乍看之下真的不太好思考，如果想要找出貪心選擇，難道是每次要選擇一個最好的數字丟進最好的軌道嗎？

別忘了我們從貪心法 II 學過的，面對這種題目，我們會需要先看出題目的本質才會比較好思考。

注意到單一軌道內的數字在進入後就無法改變相對順序了，當所有數字都進入軌道後，我們所能控制的，就只有他們從軌道出來的順序。因此，其實問題可以重新改寫成以下形式：

• 給定一個排列，請問他是否能拆成 $k$ 個子序列，滿足每個子序列都遞增？

更直接一點，我們可以直接來解這個問題：

• 給定一個排列，請問他是能拆成最少幾個子序列，滿足每個子序列都遞增？

從這個角度思考，我們似乎可以一個一個數字從左到右照順序看過去，維護盡量少個子序列，滿足每個都遞增；在遇到一個新的數字後，找到一個最好的子序列把它放在後面就好，如果沒有符合的子序列，才新增一個。

這樣的策略只剩下最後一個疑慮：

• 在遇到一個新的數字後，哪一個子序列才是對他來說最好的呢？

很明顯的，該數字如果是 $x$，那他能放在後面的子序列尾端的數字肯定得 $<x$，若沒有這樣的子序列，$x$ 就得新開一個子序列。

當有多個子序列可以讓 $x$ 做選擇時，其實有一個很乾脆的結論：

• 選擇這些可選子序列中，尾端最大的那個。

證明其實也很單純，假設這個最大的尾端是 $b$，最佳解卻選擇了 $a$ 的話，我們與最佳解在這瞬間的差異就是兩個子序列的尾端：最佳解是 $\{b, x\}$、我們則是 $\{a, x\}$。可以發現，我們「後續能承受的」只會比這個所謂的最佳解還要更寬裕，也就間接證明了最佳解可以直接貼合我們的策略。

不過事情當然沒那麼單純，一樣的，因為我們每次放數字都可能有 $k$ 個子序列要考慮，這會讓時間複雜度直接上升到 $O(nk)$，實在不太樂見。

我們不妨先假設這 $k$ 個子序列已經按照尾端排好了，觀察看看新的數字加進來後會發生什麼事：

如果原本的序列如下所示，要加進來的數字是 $6$，則他會放在下列紅色的數字所代表的子序列後方：

$$
1\ 3\ \color{red}{5}\ 8\ 9
$$

放完後會變成

$$
1\ 3\ \color{red}{6}\ 8\ 9
$$

讀者是否有發現什麼呢？放完之後，整個序列還是遞增的！而且這個性質就算是遇到「新增一個子序列」的情況，放在最後面也當然是吻合的。

這代表說，我們每次其實就只是嘗試在一個遞增的序列中，找到 $< x$ 中的最大位置，好好與我們學過的技巧做連結——這個不正是一個二分搜能辦到的事情嗎？

因此，利用二分搜來模擬數字放在後方的過程，整體就是一個 $O(N\log N)$ 的演算法。

讓我們回顧一下放在基礎演算法 / 對答案二分搜的這道習題。按照當時所學的，這題很直接就是先對答案二分搜，將問題轉化成「當服務半徑是 $R$ 時，最少要蓋幾個基地台才能蓋住所有服務點」。

注意到此時，我們可以把一個基地台的設置想成是我們把一個長度為 $2R$ 的區間覆蓋在數線上，而最後要的就是讓所有服務點都被區間蓋住。相信讀者都來到這裡了，便能直接想出最為單純的貪心策略：每次找到最左邊還沒被覆蓋的那個服務點後，直接設置一個基地台使得他的區間左界蓋著這個服務點。

這樣的問題能給我們什麼啟發呢？有些讀者可能沒有意識到，但實際上包含我們在基礎演算法 / 對答案二分搜所學的，這些問題很多都是先對答案二分搜後，變成在解一個「貪心法」的問題！

換句話說，一道貪心法的題目並不一定會裸裸的呈現在我們面前的，反而很有可能需要經過一層拆解才能可以得到我們要需要解的問題——在這裡，我們就是透過對答案二分搜來拆解出背後的貪心法題目。

在這個章節，我們了解到了兩種貪心可能可以跟其他領域結合的可能性：

• 先得出一個貪心策略，再使用資料結構優化。
• 貪心法的題目可能會藏在一層包裝下——在本文章中，我們了解到先「對答案二分搜」會是一種常見的包裝。

當然，看過這些例子後，相信有些讀者可能便會有這樣的疑問：

• 貪心法還有可能跟其他演算法結合嗎？

答案是肯定的，但其涉及的概念將會更深入一些。做為階段性的學習任務，我們就先在這裡停下來，讓讀者把目前階段的知識吸收完整後，未來就能夠更扎實的理解後續的延伸。

希望本章節能初步讓讀者認識到，在思考題目時不要總是往單一演算法或是資料結構去思考，而是將問題做出仔細的拆解後，逐步找出每一個部份分別需要用什麼樣的技巧擊破，才能夠設計出一個完整的演算法。