题目描述
给你一个下标从 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,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 。
示例 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
解法
方法一：贪心 + 前缀和 + 二分查找
我们考虑枚举 Alice 的站立位置 $i$，对于每个 $i$，我们按照如下的策略进行操作：
- 首先，如果位置 $i$ 的数字为 $1$，我们可以直接拾取一个 $1$，不需要行动次数。
- 然后，我们对 $i$ 的左右两侧位置的数字 $1$ 进行拾取，执行的是行动 $2$，即把位置 $i-1$ 的 $1$ 移到位置 $i$，然后拾取；把位置 $i+1$ 的 $1$ 移到位置 $i$，然后拾取。每拾取一个 $1$，需要 $1$ 次行动。
- 接下来，我们最大限度地将 $i-1$ 或 $i+1$ 上的 $0$，利用行动 $1$，将其置为 $1$，然后利用行动 $2$，将其移动到位置 $i$，拾取。直到拾取的 $1$ 的数量达到 $k$ 或者行动 $1$ 的次数达到 $\textit{maxChanges}$。我们假设行动 $1$ 的次数为 $c$，那么总共需要 $2c$ 次行动。
- 利用完行动 $1$，如果拾取的 $1$ 的数量还没有达到 $k$，我们需要继续考虑在 $[1,..i-2]$ 和 $[i+2,..n]$ 的区间内，进行行动 $2$，将 $1$ 移动到位置 $i$，拾取。我们可以使用二分查找来确定这个区间的大小，使得拾取的 $1$ 的数量达到 $k$。具体地，我们二分枚举一个区间的大小 $d$，然后在区间 $[i-d,..i-2]$ 和 $[i+2,..i+d]$ 内，进行行动 $2$，将 $1$ 移动到位置 $i$，拾取。如果拾取的 $1$ 的数量达到 $k$，我们就更新答案。
时间复杂度 $O(n \times \log n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\textit{nums}$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | class Solution:
def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:
n = len(nums)
cnt = [0] * (n + 1)
s = [0] * (n + 1)
for i, x in enumerate(nums, 1):
cnt[i] = cnt[i - 1] + x
s[i] = s[i - 1] + i * x
ans = inf
max = lambda x, y: x if x > y else y
min = lambda x, y: x if x < y else y
for i, x in enumerate(nums, 1):
t = 0
need = k - x
for j in (i - 1, i + 1):
if need > 0 and 1 <= j <= n and nums[j - 1] == 1:
need -= 1
t += 1
c = min(need, maxChanges)
need -= c
t += c * 2
if need <= 0:
ans = min(ans, t)
continue
l, r = 2, max(i - 1, n - i)
while l <= r:
mid = (l + r) >> 1
l1, r1 = max(1, i - mid), max(0, i - 2)
l2, r2 = min(n + 1, i + 2), min(n, i + mid)
c1 = cnt[r1] - cnt[l1 - 1]
c2 = cnt[r2] - cnt[l2 - 1]
if c1 + c2 >= need:
t1 = c1 * i - (s[r1] - s[l1 - 1])
t2 = s[r2] - s[l2 - 1] - c2 * i
ans = min(ans, t + t1 + t2)
r = mid - 1
else:
l = mid + 1
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46 | class Solution {
public long minimumMoves(int[] nums, int k, int maxChanges) {
int n = nums.length;
int[] cnt = new int[n + 1];
long[] s = new long[n + 1];
for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + i * nums[i - 1];
}
long ans = Long.MAX_VALUE;
for (int i = 1; i <= n; ++i) {
long t = 0;
int need = k - nums[i - 1];
for (int j = i - 1; j <= i + 1; j += 2) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] == 1) {
--need;
++t;
}
}
int c = Math.min(need, maxChanges);
need -= c;
t += c * 2;
if (need <= 0) {
ans = Math.min(ans, t);
continue;
}
int l = 2, r = Math.max(i - 1, n - i);
while (l <= r) {
int mid = (l + r) >> 1;
int l1 = Math.max(1, i - mid), r1 = Math.max(0, i - 2);
int l2 = Math.min(n + 1, i + 2), r2 = Math.min(n, i + mid);
int c1 = cnt[r1] - cnt[l1 - 1];
int c2 = cnt[r2] - cnt[l2 - 1];
if (c1 + c2 >= need) {
long t1 = 1L * c1 * i - (s[r1] - s[l1 - 1]);
long t2 = s[r2] - s[l2 - 1] - 1L * c2 * i;
ans = Math.min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58 | class Solution {
public:
long long minimumMoves(vector<int>& nums, int k, int maxChanges) {
int n = nums.size();
vector<int> cnt(n + 1, 0);
vector<long long> s(n + 1, 0);
for (int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + 1LL * i * nums[i - 1];
}
long long ans = LLONG_MAX;
for (int i = 1; i <= n; ++i) {
long long t = 0;
int need = k - nums[i - 1];
for (int j = i - 1; j <= i + 1; j += 2) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] == 1) {
--need;
++t;
}
}
int c = min(need, maxChanges);
need -= c;
t += c * 2;
if (need <= 0) {
ans = min(ans, t);
continue;
}
int l = 2, r = max(i - 1, n - i);
while (l <= r) {
int mid = (l + r) / 2;
int l1 = max(1, i - mid), r1 = max(0, i - 2);
int l2 = min(n + 1, i + 2), r2 = min(n, i + mid);
int c1 = cnt[r1] - cnt[l1 - 1];
int c2 = cnt[r2] - cnt[l2 - 1];
if (c1 + c2 >= need) {
long long t1 = 1LL * c1 * i - (s[r1] - s[l1 - 1]);
long long t2 = s[r2] - s[l2 - 1] - 1LL * c2 * i;
ans = min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | func minimumMoves(nums []int, k int, maxChanges int) int64 {
n := len(nums)
cnt := make([]int, n+1)
s := make([]int, n+1)
for i := 1; i <= n; i++ {
cnt[i] = cnt[i-1] + nums[i-1]
s[i] = s[i-1] + i*nums[i-1]
}
ans := math.MaxInt64
for i := 1; i <= n; i++ {
t := 0
need := k - nums[i-1]
for _, j := range []int{i - 1, i + 1} {
if need > 0 && 1 <= j && j <= n && nums[j-1] == 1 {
need--
t++
}
}
c := min(need, maxChanges)
need -= c
t += c * 2
if need <= 0 {
ans = min(ans, t)
continue
}
l, r := 2, max(i-1, n-i)
for l <= r {
mid := (l + r) >> 1
l1, r1 := max(1, i-mid), max(0, i-2)
l2, r2 := min(n+1, i+2), min(n, i+mid)
c1 := cnt[r1] - cnt[l1-1]
c2 := cnt[r2] - cnt[l2-1]
if c1+c2 >= need {
t1 := c1*i - (s[r1] - s[l1-1])
t2 := s[r2] - s[l2-1] - c2*i
ans = min(ans, t+t1+t2)
r = mid - 1
} else {
l = mid + 1
}
}
}
return int64(ans)
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55 | function minimumMoves(nums: number[], k: number, maxChanges: number): number {
const n = nums.length;
const cnt = Array(n + 1).fill(0);
const s = Array(n + 1).fill(0);
for (let i = 1; i <= n; i++) {
cnt[i] = cnt[i - 1] + nums[i - 1];
s[i] = s[i - 1] + i * nums[i - 1];
}
let ans = Infinity;
for (let i = 1; i <= n; i++) {
let t = 0;
let need = k - nums[i - 1];
for (let j of [i - 1, i + 1]) {
if (need > 0 && 1 <= j && j <= n && nums[j - 1] === 1) {
need--;
t++;
}
}
const c = Math.min(need, maxChanges);
need -= c;
t += c * 2;
if (need <= 0) {
ans = Math.min(ans, t);
continue;
}
let l = 2,
r = Math.max(i - 1, n - i);
while (l <= r) {
const mid = (l + r) >> 1;
const [l1, r1] = [Math.max(1, i - mid), Math.max(0, i - 2)];
const [l2, r2] = [Math.min(n + 1, i + 2), Math.min(n, i + mid)];
const c1 = cnt[r1] - cnt[l1 - 1];
const c2 = cnt[r2] - cnt[l2 - 1];
if (c1 + c2 >= need) {
const t1 = c1 * i - (s[r1] - s[l1 - 1]);
const t2 = s[r2] - s[l2 - 1] - c2 * i;
ans = Math.min(ans, t + t1 + t2);
r = mid - 1;
} else {
l = mid + 1;
}
}
}
return ans;
}
|