algorithm - 通过一次翻转 k 位来生成最大的 1

Question

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

• 恰好选择 k 位(不一定是连续的)并翻转它们的状态(0 到 1，1 到 0)；

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

• xxxx_
• xxx_x

'x'代表我们翻转那个位置的位。

但我不确定之后如何进行，我无法进行更多观察。那么，什么才是正确的做法呢？您可以假设 n^2 算法是可行的。

Answer 1

翻转零，直到零的数量低于 k。令 m 为零的个数。

翻转 k - m/2 个 1 和 m/2 个零(整数除法)。现在你有 m + (k-m/2) - m/2 = m + k - m/2 - m/2 ~ k 个零。 (整数除法的近似 b/c)。

最后，翻转所有的零，并根据需要翻转尽可能多的零，总共翻转 k 次。根据 m 的奇偶性，这将是全 1 或接近。