题目
给你一个下标从 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 所需的 最少 行动次数。
示例 1：
输入：nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1
输出：3
解释：如果游戏开始时 Alice 在 aliceIndex == 1 的位置上，按照以下步骤执行每个动作，他可以利用 3 次行动拾取 3 个 1 ：
游戏开始时 Alice 拾取了一个 1 ，nums[1] 变成了 0。此时 nums 变为 [1,1,1,0,0,1,1,0,0,1] 。
选择 j == 2 并执行第一种类型的动作。nums 变为 [1,0,1,0,0,1,1,0,0,1]
选择 x == 2 和 y == 1 ，并执行第二种类型的动作。nums 变为 [1,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [1,0,0,0,0,1,1,0,0,1] 。
选择 x == 0 和 y == 1 ，并执行第二种类型的动作。nums 变为 [0,1,0,0,0,1,1,0,0,1] 。由于 y == aliceIndex，Alice 拾取了一个 1 ，nums 变为 [0,0,0,0,0,1,1,0,0,1] 。
请注意，Alice 也可能执行其他的 3 次行动序列达成拾取 3 个 1 。
示例 2：
输入：nums = [0,0,0,0], k = 2, maxChanges = 3
输出：4
解释：如果游戏开始时 Alice 在 aliceIndex == 0 的位置上，按照以下步骤执行每个动作，他可以利用 4 次行动拾取 2 个 1 ：
选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于 y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。
再次选择 j == 1 并执行第一种类型的动作。nums 变为 [0,1,0,0] 。
再次选择 x == 1 和 y == 0 ，并执行第二种类型的动作。nums 变为 [1,0,0,0] 。由于y == aliceIndex，Alice 拾起了一个 1 ，nums 变为 [0,0,0,0] 。
提示：
- $2 <= n <= 10^5$
- $0 <= nums[i] <= 1$
- $1 <= k <= 10^5$
- $0 <= maxChanges <= 10^5$
- $maxChanges + sum(nums) >= k$
分析
- 任意位置开始
- 行动规则：
- 选择另外一个坐标 j，值为0，重置为1。这个动作最多执行maxChanges
- 这个动作是给第二个动作制造机会，拾取1
- 选择相邻的坐标x,y，一个为1和另一个为0，值互换，将1重置为0。完成拾起一个1
- 选择另外一个坐标 j，值为0，重置为1。这个动作最多执行maxChanges
贪心策略
- 记录1的下标数组
- 记录连续1的 最长长度
class Solution {
public long minimumMoves(int[] nums, int k, int maxChanges) {
List<Integer> pos = new ArrayList<>();
int c = 0; // nums 中连续的 1 长度
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) continue;
pos.add(i); // 记录 1 的位置
c = Math.max(c, 1);
if (i > 0 && nums[i - 1] == 1) {
if (i > 1 && nums[i - 2] == 1) {
c = 3; // 有 3 个连续的 1
} else {
c = Math.max(c, 2); // 有 2 个连续的 1
}
}
}
c = Math.min(c, k);
if (maxChanges >= k - c) {
// 其余 k-c 个 1 可以全部用两次操作得到
return Math.max(c - 1, 0) + (k - c) * 2;
}
int n = pos.size();
long[] sum = new long[n + 1];
for (int i = 0; i < n; i++) {
sum[i + 1] = sum[i] + pos.get(i);
}
long ans = Long.MAX_VALUE;
// 除了 maxChanges 个数可以用两次操作得到，其余的 1 只能一步步移动到 pos[i]
int size = k - maxChanges;
for (int right = size; right <= n; right++) {
// s1+s2 是 j 在 [left, right) 中的所有 pos[j] 到 index=pos[(left+right)/2] 的距离之和
int left = right - size;
int i = left + size / 2;
long index = pos.get(i);
long s1 = index * (i - left) - (sum[i] - sum[left]);
long s2 = sum[right] - sum[i] - index * (right - i);
ans = Math.min(ans, s1 + s2);
}
return ans + maxChanges * 2;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
