中位数贪心，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;
};