難度: Hard
目前下列解法的時間複雜度: O(n/k*lg(n/k)*k) = O(n*lg(n/k))
題目說明
(原提意)
給定一長度 n 的 0-indexed 的陣列,及一個 k , 0 < k <=陣列長度。
每次你可以改變陣列中任一個元素至任意值。
求:讓陣列中每個元素不大於其往後數 k 個位置的元素,所需要的改變次數。
(對於所有 k <= i < n ,陣列[i-k] <= 陣列[i])
(轉換後題意)
求 k 次非嚴格遞增的 LIS 長度,並加總該 LIS 長度與原序列長度的差值。
解法:LIS * k次
1. 所以簡單來說就是做 這題 http://www.jamesdambrosio.com/creationDetail.php?sn=5237583 , k 次。
2. 結束了。
source code
延伸:
1. 觀察使用 lower_bound 與 upper_bound 的差別。
好耶, 100%