前往
大廳
主題

[leetcode]2111. Minimum Operations to Make the Array K-Increasing

♙♲⚙\~O_O~/⚙♲♙ | 2021-12-21 12:21:00 | 巴幣 8 | 人氣 308

題目: 2111. Minimum Operations to Make the Array K-Increasing
難度: 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. 所以簡單來說就是做 這題 https://home.gamer.com.tw/creationDetail.php?sn=5237583 , k 次。
2. 結束了。


source code

延伸:
1. 觀察使用 lower_bound 與 upper_bound 的差別。


ㄏㄚˊ,比賽有 sponsor 就要填資料ㄛ?跳過啦
好耶, 100%


創作回應

Ctrl+Shift+W
佬欸
2021-12-21 15:34:15

相關創作

更多創作