每次翻转k个比特位，使最多数量的1变为1。

Question

给定一个n位的向量和一个整数k，其中1 <= k <= n，我们必须通过任意次（包括零次）应用以下操作来最大化其中的1的数量:

• 选择恰好k个位（不一定连续）并翻转它们的状态（0变为1，1变为0）；

经过一些分析，我得出了结论，如果n > k，则我们也可以同时翻转任意两个位。例如，对于n = 5，k = 4。我们可以像这样做，只翻转后两位。

• xxxx_
• xxx_x

'x'表示我们要翻转该位置上的位。

但是我不确定在此之后如何进行，并且我无法再做出更多的观察。那么，正确的方法是什么？您可以假设n²算法是可行的。

- Manish Chandra Joshi

---

如果 n-k 很小，那么朴素的 O(n^k) 方法可能已经足够快。 - MrSmith42

@MrSmith42 很遗憾，n-k并不能保证足够小。不过，你能分享一下朴素的解决方案吗？我无法想象任何暴力破解的方法。 - Manish Chandra Joshi

这个问题应该会给你一个很好的开端。 - user4668606

Answer 1

将0翻转，直到0的数量少于k个。令m为0的数量。

翻转k-m/2个1和m/2个0（整数除法）。现在你有m + (k-m/2) - m/2 = m + k - m/2 - m/2 ~ k个0。（近似值是由于整数除法）

最后，翻转所有的0和尽可能多的1，以获得总共k次翻转。这将是全部1或接近1，具体取决于m的奇偶性。

原始答案: "最初的回答"

- Dave

Answer 2

Dave的方法似乎是正确的。我会分享我在这里发布问题后想出来的方法。

假设0的数量为z，现在你要让自己相信，如果k < n，我们可以通过使用问题中提到的k位操作的组合来翻转任意两个位（一对）。以下是一个论点，帮助您满足自己对这个事实的认识：选择除了您想翻转的一对之外的任何k-1位；然后从该对中选择一个位以及我们刚刚选定的k-1位，应用该操作；然后再次选择该对中的另一个位以及我们之前选定的相同的k-1位，再次应用该操作。如果k < n或n至少为k + 1，我们保证找到这k-1个辅助位。

因此，自然地出现了两种情况：

• k == n：显然，我们只能全部翻转或者全部不翻转。因此答案是max(n - z, z)
• k < n：在这种情况下，我们可以翻转任意k位或者使用上面的方法翻转任意2位。现在，如果z < k，我们只能使用2位翻转，如果z是奇数，则还剩下一位为0，答案是n-1；如果z是偶数，则将它们全部翻转成1，答案是n。当z >= k时，我们可以同时使用k位翻转和2位翻转，如果z是奇数且k是偶数，我们还剩下一位0（答案是n-1），否则我们总是可以将所有0变成1（答案是n）。

最后一个声明的解释：如果我们既可以使用k位翻转，也可以使用2位翻转，并且z恰好为奇数，我们尝试使用一个k位翻转来改变剩余0的奇偶性（即z-k的奇偶性）。只有当k是奇数时，我们才能这样做。否则我们无法这样做，对奇数个零使用2位操作会使我们只剩下一个零。因此，简而言之，如果k是偶数且z为奇数，则我们将只剩下一个0，否则我们将得到全部1。

- Manish Chandra Joshi