Minimum Moves to Pick K Ones
You are given a binary array nums of length n, a positive integer k, and a non-negative integer maxChanges.
Alice plays a game where the goal is to pick up k ones from nums using the minimum number of moves. When the game starts, Alice chooses any index aliceIndex in the range [0, n - 1] and stands there. If nums[aliceIndex] == 1, Alice picks up the one and nums[aliceIndex] becomes 0; this does not count as a move.
After this, Alice can make any number of moves, including zero, where in each move Alice must perform exactly one of the following actions:
- Select any index
j != aliceIndexsuch thatnums[j] == 0and setnums[j] = 1. This action can be performed at mostmaxChangestimes. - Select any two adjacent indices
xandywhere|x - y| == 1,nums[x] == 1, andnums[y] == 0, then swap their values by settingnums[y] = 1andnums[x] = 0. Ify == aliceIndex, Alice picks up the one after this move andnums[y]becomes0.
Return the minimum number of moves required by Alice to pick exactly k ones.
Example 1
Input
nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1Output
3By standing at index 1, Alice can pick the initial one, create a one at index 2 and move it in, then move the one from index 0 in, for a total of 3 moves.
Example 2
Input
nums = [0,0,0,0], k = 2, maxChanges = 3Output
4Alice can stand at index 0, create a one at index 1 and move it into index 0 twice, requiring 4 total moves.
Constraints
- 2 <= n <= 10^5
- 0 <= nums[i] <= 1
- 1 <= k <= 10^5
- 0 <= maxChanges <= 10^5
- maxChanges + sum(nums) >= k