中位数贪心，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、原题链接
二、解题报告
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 = 0
for i, x in enumerate(nums):
if x == 0:
continue
pos.append(i)
c = fmax(c, 1)
if i > 0 and nums[i - 1]:
if i > 1 and nums[i - 2]:
c = 3
c = fmax(c, 2)
c = fmin(c, k)
if maxChanges >= k - c:
return fmax(c - 1, 0) + (k - c) * 2
n = len(pos)
acc = list(accumulate(pos, initial=0))
res = inf
sz = k - maxChanges
for r in range(sz, n + 1):
l = r - sz
mid = l + sz // 2
s1 = 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;
};原文地址：https://blog.csdn.net/EQUINOX1/article/details/140181951
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！