2024-10-13:用go语言,给定一个二进制数组 nums,长度为 n,
目标是让 Alice 通过最少的行动次数从 nums 中拾取 k 个1。
Alice可以选择任何索引 aliceIndex,如果对应的 nums[aliceIndex] 是1,Alice会拾取一个1并将其设为0。
之后,Alice可以选择以下两种行动之一:
将一个0变为1(最多执行 maxChanges 次),或交换相邻的两个数(一个是1,一个是0)。
返回拾取 k 个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,0,0,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 。
相似问题