• Leetcode 3505. Minimum Operations to Make Elements Within K Subarrays Equal
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3505. Minimum Operations to Make Elements Within K Subarrays Equal

1. 解題思路

這一題大的思路上不難想到就是一個動態規劃的思路。我們分別考察每一個位置是否需要作為某一個子串的開始位置，然后考察對應子串要使之變為完全相同所需要的最小操作數，然后找出其總和的最小值即可。其總體的算法復雜度在不考慮求子串的最小操作數的情況下就會是$O(NK)$。

但是，這復雜度還是很高的，因此，也就要求我們事實上對于上述子問題，即給定一個長度為x的數組，求令其變得完全相同時所需的最小操作數，的算法復雜度要求就會非常高，至少不是一個滑動窗口遍歷的$O(X)$可以處理的，我們需要將其壓縮至$O(logX)$甚至$O(1)$。

萬幸的是，通過數學分析，我們可以知道對于一個給定一個長度為x的數組，其所需的最小操作數一定就是將其全部變為其中位數時所需的操作數。而基于此，我們可以提前先算出每一個位置作為起始位置時其長度為x的數組的最小操作數，此時我們可以通過前一個位置的結果進行調整，兩者變動的元素至多只有一個，因此我們可以復用之前的結果從而省略掉排序的過程，整體的算法復雜度就會是$O(NlogX)$。

此時，總的題目的算法復雜度就會是$O(NK+NlogX)$，整體就還勉強在允許范圍內了。

2. 代碼實現

給出python代碼實現如下：

class Solution:def minOperations(self, nums: List[int], x: int, k: int) -> int:n = len(nums)min_ops = [math.inf for i in range(n-x+1)]sub = sorted(nums[:x])m = (x+1) // 2left, ls = sub[:m], sum(sub[:m])right, rs = sub[m:], sum(sub[m:])min_ops[0] = (m*2-x) * left[-1]  - ls + rsfor i in range(n-x):if bisect.bisect_left(left, nums[i]) < m:left.pop(bisect.bisect_left(left, nums[i]))ls -= nums[i]else:right.pop(bisect.bisect_left(right, nums[i]))rs -= nums[i]bisect.insort(left, nums[i+x])ls += nums[i+x]while len(left) < m:elem = right.pop(0)rs -= elembisect.insort(left, elem)ls += elemwhile len(left) > m:elem = left.pop(-1)ls -= elembisect.insort(right, elem)rs += elemwhile left[-1] > right[0]:l, r = left.pop(-1), right.pop(0)bisect.insort(left, r)bisect.insort(right, l)ls = ls - l + rrs = rs - r + lmin_ops[i+1] = (m*2-x) * left[-1]  - ls + rs@lru_cache(maxsize = 10000)def dp(idx, k):if k == 0:return 0if idx >= n:return math.inf if idx+k*x > n:return math.infelif idx+k*x == n:return min_ops[idx] + dp(idx+x, k-1)return min(dp(idx+1, k), min_ops[idx] + dp(idx+x, k-1))return dp(0, k)

提交代碼評測得到：耗時4845ms，占用內存194MB。