| comments | difficulty | edit_url | rating | source | tags | ||||
|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2672 |
第 389 场周赛 Q4 |
|
给你一个下标从 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 <= 1050 <= nums[i] <= 11 <= k <= 1050 <= maxChanges <= 105maxChanges + sum(nums) >= k