更改数组中的最小条目数，使任意 k 个连续项的总和为偶数

Question

我们得到了一个整数数组。我们必须根据需要更改这些整数的最小数量，以便对于某个固定参数 k，数组中任意 k 个连续项的总和为偶数。 示例：

N = 8; K = 3; A = {1,2,3,4,5,6,7,8}

我们可以改变 3 个元素 (4th,5th,6th) 所以数组可以是 {1,2,3,5,6,7,7, 8} 然后

1+2+3=6为偶数
2+3+5=10为偶数
3+5+6=14为偶数
5+6+7=18为偶数
6+7+7=20为偶数
7+7+8=22为偶数

Answer 1

这个问题有一个很好的 O(n) 时间解决方案，在较高层次上，它的工作原理如下：

认识到确定要翻转的项目归结为确定在要翻转的项目的数组中重复的模式。
使用动态规划来确定该模式是什么。

下面是如何得出这个解决方案。

首先，一些观察。因为我们在这里只关心总和是偶数还是奇数，所以我们实际上并不关心数字的确切值。我们只关心它们是偶数还是奇数。因此，让我们首先用 0（如果数字是偶数）或 1（如果是奇数）替换每个数字。现在，我们的任务是让每个 window 的 k 个元素都有偶数个 1。

其次，转换数组后产生的 0 和 1 的模式具有令人惊讶的形状：它只是数组前 k 个元素的重复副本。例如，假设 k = 5，我们决定数组应该以 1 0 1 1 1 开头。第六个数组元素必须是什么？好吧，在从第一个 window 移动到第二个时，我们从 window 的前面删除了一个 1，将奇偶校验更改为奇偶校验。因此，我们必须让下一个数组元素为 1，这意味着第六个数组元素必须为 1，等于第一个数组元素。第七个数组元素必须是 0，因为在从第二个 window 移动到第三个时，我们删除了一个零。这个过程意味着无论我们为前 k 个元素决定什么，结果都会决定整个最终的值序列。

这意味着我们可以通过以下方式重构问题：将 n 个项目的原始输入数组分解为 n/k 个大小为 k 的块。我们现在被要求选择一个 0 和 1 的序列，使得

此序列与 n/k 块的不同之处尽可能少，每个块有 k 个项目，并且
该序列有偶数个 1。

例如，给定输入序列

0 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

和 k = 3，我们将形成块

0 1 1, 0 1 1, 1 0 0, 1 0 1, 1 1 0, 1 1 1

然后尝试找到一个长度为 3 且其中包含偶数个 1 的模式，以便用该模式替换每个块需要最少的编辑次数。

让我们看看如何解决这个问题。让我们一次一点地工作。例如，我们可以问：让第一个位为 0 的成本是多少？使第一个位为 1 的成本是多少？使第一个位为 0 的成本等于前面有 1 的块的数量，使第一个位为 1 的成本等于前面有 0 的块的数量。我们可以算出将每一位单独设置为零或一的成本。这给了我们一个像这样的矩阵：

                       Bit #0   Bit #1   Bit #2   Bit #3     ...   Bit #k-1
---------------------+--------+--------+--------+--------+--------+----------
Cost of setting to 0 |        |        |        |        |        |        |
Cost of setting to 1 |        |        |        |        |        |        |

我们现在需要为每一列选择一个值，以最小化选择的总成本为目标，受制于我们选择偶数位等于 1 的约束。这是一个很好的动态规划锻炼。我们考虑

形式的子问题

What is the lowest cost you can make out of the first m columns from the table, provided your choice has parity p of items chosen from the bottom row?

我们可以将其存储在 (k + 1) × 2 table T[m][p] 中，例如，T[3][even] 是您可以实现的最低成本使用前三列的偶数项设置为 1，T[6][odd] 是使用前六列的奇数项设置为 1 的最低成本。这给出了以下循环:

T[0][even] = 0（使用零列不花钱）
T[0][odd] = ∞（如果不使用列，则不能将奇数位设置为 1）
T[m+1][p] = min(T[m][p] + 将此位设置为 0 的成本，T[m][!p] + 将此位设置为 1 的成本) （要么使用零并保持相同的奇偶校验，要么使用 1 并翻转奇偶校验）。

这可以在时间 O(k) 中进行评估，得到的最小成本由 T[n][even] 给出。您可以使用标准 DP table 步行从该点重建最优解。

总的来说，这是最终算法：

create a table costs[k+1][2], all initially zero.

/* Populate the costs table. costs[m][0] is the cost of setting bit m
 * to 0; costs[m][1] is the cost of setting bit m to 1. We work this
 * out by breaking the input into blocks of size k, then seeing, for
 * each item within each block, what its parity is. The cost of setting
 * that bit to the other parity then increases by one.
 */
for i = 0 to n - 1:
    parity = array[i] % 2
    costs[i % k][!parity]++ // Cost of changing this entry

/* Do the DP algorithm to find the minimum cost. */
create array T[k + 1][2]
T[0][0] = 0
T[0][1] = infinity

for m from 1 to k:
    for p from 0 to 1:
        T[m][p] = min(T[m - 1][p]  + costs[m - 1][0],
                      T[m - 1][!p] + costs[m - 1][1])

return T[m][0]

总的来说，我们在初始通道中执行 O(n) 的工作来计算将每个位独立设置为 0 的成本。然后我们在最后的 DP 步骤中执行 O(k) 的工作。因此，整体工作量为 O(n + k)，假设 k ≤ n（否则问题微不足道）成本为 O(n).

更改数组中的最小条目数，使任意 k 个连续项的总和为偶数

Change the minimum number of entries in an array so that the sum of any k consecutive items is even

arrays

algorithm

dynamic-programming

parity