STEP5 Problem 0022 : 掉落的橘子

題目：

給一長度為 N 的不遞減數列，在其中選定一個基準點，每個數被選取的代價為與

基準點的距離，給定一個 K 值，代表總代價的最大值，請求出基準點在最佳位置

時，最多可以選取多少個數？

(N <= 5000000)


解法：

首先，若區間左右界已經定下，可以知道最佳位置必在這些數字中的「中位數」

上，此時總 cost 一定會最小(列出數學式可以簡單證明)，於是問題轉換成，如何

選定一個最佳的區間使得可以選取最多的數字，我們可以用一個 deque 來維護

整個區間，若當前 cost <= K 時，就由右端加入數字，並且更新目前的最佳位置

及 cost ，若當前 cost > K 時，將左端數字拿掉，直到 cost <= K 為止，記錄過程

中最大的區間即可得到答案。

由於每個數都被加入和刪除一次，透過動態維護變數可以 O(1) 更新最佳位置

故總時間複雜度為 O(N) 。