中位数贪心，3086. 拾起 K 个 1 需要的最少行动次数
一、题目
1、题目描述
给你一个下标从 0 开始的二进制数组
nums，其长度为n；另给你一个 正整数k以及一个 非负整数maxChanges。Alice 在玩一个游戏，游戏的目标是让 Alice 使用 最少 数量的 行动 次数从
nums中拾起k个 1 。游戏开始时，Alice 可以选择数组[0, n - 1]范围内的任何索引aliceIndex站立。如果nums[aliceIndex] == 1，Alice 会拾起一个 1 ，并且nums[aliceIndex]变成0（这 不算 作一次行动）。之后，Alice 可以执行 任意数量 的 行动（包括零次），在每次行动中 Alice 必须 恰好 执行以下动作之一：
- 选择任意一个下标
j != aliceIndex且满足nums[j] == 0，然后将nums[j]设置为1。这个动作最多可以执行maxChanges次。- 选择任意两个相邻的下标
x和y（|x - y| == 1）且满足nums[x] == 1,nums[y] == 0，然后交换它们的值（将nums[y] = 1和nums[x] = 0）。如果y == aliceIndex，在这次行动后 Alice 拾起一个 1 ，并且nums[y]变成0。返回 Alice 拾起 恰好
k个 1 所需的 最少 行动次数。
2、接口描述
python3
class Solution:def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:cpp
class Solution {
public:long long minimumMoves(vector<int>& nums, int k, int maxChanges) {}
};js
/*** @param {number[]} nums* @param {number} k* @param {number} maxChanges* @return {number}*/
var minimumMoves = function(nums, k, maxChanges) {};
3、原题链接
3086. 拾起 K 个 1 需要的最少行动次数
二、解题报告
1、思路分析
操作1其实就是提供了一种两步得到1的方案
我们考虑两步一个1一定是最优的吗？
如果1、2、3个连续个1，我们发现此时分别需要0、1、2步
所以这道题是有corner case的
我们这样考虑
3个以内的连续1的最大连续长度记为c，如果拿掉c个剩下的1可以都通过2步得到
我们的答案就是c - 1 + (k - c) * 2
否则，问题就变成了一个很简单的中位数贪心问题
扫描一遍k - maxChanges的窗口，O(1)计算其中位数贪心下的解维护最优解即可
2、复杂度
时间复杂度： O(N)空间复杂度：O(N)
3、代码详解
python3
fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
class Solution:def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:pos = []c = 0for i, x in enumerate(nums):if x == 0:continuepos.append(i)c = fmax(c, 1)if i > 0 and nums[i - 1]:if i > 1 and nums[i - 2]:c = 3c = fmax(c, 2)c = fmin(c, k)if maxChanges >= k - c:return fmax(c - 1, 0) + (k - c) * 2n = len(pos)acc = list(accumulate(pos, initial=0))res = infsz = k - maxChangesfor r in range(sz, n + 1):l = r - szmid = l + sz // 2s1 = pos[mid] * (mid - l) - (acc[mid] - acc[l])s2 = acc[r] - acc[mid] - pos[mid] * (r - mid)res = fmin(res, s1 + s2)return res + maxChanges * 2
cpp
class Solution {
public:long long minimumMoves(vector<int>& nums, int k, int maxChanges) {int c = 0;std::vector<int> pos;for (int i = 0, n = nums.size(); i < n; i ++ ) {if (!nums[i]) continue;pos.push_back(i);c = max(c, 1);if (i && nums[i - 1]) {if (i > 1 && nums[i - 2])c = 3;c = max(c, 2);}}c = min(c, k);if (maxChanges >= k - c)return max(c - 1, 0) + (k - c) * 2;int n = pos.size(), sz = k - maxChanges;std::vector<long long> acc(n + 1);for (int i = 0; i < n; i ++ ) acc[i + 1] = acc[i] + pos[i];long long res = 1e10;for (int r = sz; r <= n; r ++ ) {int l = r - sz, mid = l + sz / 2;long long s1 = 1LL * pos[mid] * (mid - l) - (acc[mid] - acc[l]);long long s2 = acc[r] - acc[mid] - 1LL * pos[mid] * (r - mid);res = min(res, s1 + s2);\}return res + maxChanges * 2LL;}
};js
/*** @param {number[]} nums* @param {number} k* @param {number} maxChanges* @return {number}*/
var minimumMoves = function(nums, k, maxChanges) {let c = 0;let pos = [];for (let i = 0; i < nums.length; i ++ ) {if (nums[i] == 0) continue;pos.push(i);c = Math.max(c, 1);if (i && nums[i - 1]) {if (i > 1 && nums[i - 2])c = 3;c = Math.max(c, 2);}}c = Math.min(c, k);if (maxChanges >= k - c)return Math.max(c - 1, 0) + (k - c) * 2;let n = pos.length;let acc = new Array(n + 1).fill(0);for (let i = 0; i < n; i ++ )acc[i + 1] = pos[i] + acc[i];let res = Infinity, sz = k - maxChanges;for (let r = sz; r <= n; r ++ ) {let l = r - sz, mid = l + parseInt(sz / 2);let s1 = pos[mid] * (mid - l) - (acc[mid] - acc[l]);let s2 = acc[r] - acc[mid] - pos[mid] * (r - mid);res = Math.min(res, s1 + s2);}return res + maxChanges * 2;
};