3086. Minimum Moves to Pick K Ones Hard

1/**
2 * [3086] Minimum Moves to Pick K Ones
3 *
4 * You are given a binary array nums of length n, a positive integer k and a non-negative integer maxChanges.
5 * Alice plays a game, where the goal is for Alice to pick up k ones from nums using the minimum number of moves. When the game starts, Alice picks up 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:
6 * 
7 * 	Select any index j != aliceIndex such that nums[j] == 0 and set nums[j] = 1. This action can be performed at most maxChanges times.
8 * 	Select any two adjacent indices x and y (|x - y| == 1) such that nums[x] == 1, nums[y] == 0, then swap their values (set nums[y] = 1 and nums[x] = 0). If y == aliceIndex, Alice picks up the one after this move and nums[y] becomes 0.
9 * 
10 * Return the minimum number of moves required by Alice to pick exactly k ones.
11 *  
12 * <strong class="example">Example 1:
13 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
14 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">nums = [1,1,0,0,0,1,1,0,0,1], k = 3, maxChanges = 1</span>
15 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">3</span>
16 * Explanation: Alice can pick up 3 ones in 3 moves, if Alice performs the following actions in each move when standing at aliceIndex == 1:
17 * 
18 * 	At the start of the game Alice picks up the one and nums[1] becomes 0. nums becomes [1,<u>0</u>,0,0,0,1,1,0,0,1].
19 * 	Select j == 2 and perform an action of the first type. nums becomes [1,<u>0</u>,1,0,0,1,1,0,0,1]
20 * 	Select x == 2 and y == 1, and perform an action of the second type. nums becomes [1,<u>1</u>,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [1,<u>0</u>,0,0,0,1,1,0,0,1].
21 * 	Select x == 0 and y == 1, and perform an action of the second type. nums becomes [0,<u>1</u>,0,0,0,1,1,0,0,1]. As y == aliceIndex, Alice picks up the one and nums becomes [0,<u>0</u>,0,0,0,1,1,0,0,1].
22 * 
23 * Note that it may be possible for Alice to pick up 3 ones using some other sequence of 3 moves.
24 * </div>
25 * <strong class="example">Example 2:
26 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
27 * Input: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">nums = [0,0,0,0], k = 2, maxChanges = 3</span>
28 * Output: <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;">4</span>
29 * Explanation: Alice can pick up 2 ones in 4 moves, if Alice performs the following actions in each move when standing at aliceIndex == 0:
30 * 
31 * 	Select j == 1 and perform an action of the first type. nums becomes [<u>0</u>,1,0,0].
32 * 	Select x == 1 and y == 0, and perform an action of the second type. nums becomes [<u>1</u>,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [<u>0</u>,0,0,0].
33 * 	Select j == 1 again and perform an action of the first type. nums becomes [<u>0</u>,1,0,0].
34 * 	Select x == 1 and y == 0 again, and perform an action of the second type. nums becomes [<u>1</u>,0,0,0]. As y == aliceIndex, Alice picks up the one and nums becomes [<u>0</u>,0,0,0].
35 * </div>
36 *  
37 * Constraints:
38 * 
39 * 	2 <= n <= 10^5
40 * 	0 <= nums[i] <= 1
41 * 	1 <= k <= 10^5
42 * 	0 <= maxChanges <= 10^5
43 * 	maxChanges + sum(nums) >= k
44 * 
45 */
46pub struct Solution {}
47
48// problem: https://leetcode.com/problems/minimum-moves-to-pick-k-ones/
49// discuss: https://leetcode.com/problems/minimum-moves-to-pick-k-ones/discuss/?currentPage=1&orderBy=most_votes&query=
50
51// submission codes start here
52
53impl Solution {
54    pub fn minimum_moves(nums: Vec<i32>, k: i32, max_changes: i32) -> i64 {
55        
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_3086() {
67    }
68}
69