APCS202501第3題 重組問題

題目：https://zerojudge.tw/ShowProblem?problemid=q183

出處：APCS202501

解題想法：

Step1)將所有差值放置在deque內，由小到大排序，取出最大值就是R(數列的最大值)，將此最大值R從deque刪除。接著取出差值內最大的數值dq.back()，此數值是原始差值的第二大，此時R-dq.back()或dq.back()都是可能的數列元素，其中一個或者兩個都是，遞迴find(R-du.back())與find(dq.back())。如果兩個都是，遞迴下去的dq內會有兩個相同的最大值。

Step2)find(M)，使用函式check檢查在dq內是否有M的所有差值，所有M距離兩端點以及與已經加入ans的每個點的差值，如果數量足夠(不能只檢查數值是否存在，因為同一個數值可能需要很多個)才從dq內刪除這些數值，刪除的目的是要最後找到n個數字後，dq內所有元素應該要清空，並刪除的差值記錄在tmp[]。

將M儲存在ans[]，ans[]用於產生最後的最小字典序。

從dq內刪除關於M的所有差值後，R-dq.back()或dq.back()是可能的最小字典序元素，遞迴find(R-dq.back())與find(dq.back())

萬一往下遞迴時，發現找不到解時，退回此步驟時，需從ans[]刪除M，使用tmp[]復原dq，重新由小到大排序。

Step3)找到最小字典序就不再遞迴下去，使用變數success，預設為false，當success設定為true，不再遞迴，表示已經找到最小字典序。

Step4)最大字典序可以使用最小字典序算出。