讨论/技术交流/[K连续位的最小翻转次数]的贪心算法的正确性证明/
[K连续位的最小翻转次数]的贪心算法的正确性证明

我写了关于今天的每日一题K连续位的最小翻转次数的贪心算法的正确性的证明,大家帮忙看看有没有错误,欢迎指出,一起完善一下,谢谢!

思路及正确性证明
我们从左到右遍历数组,每次遇到 0,就将从当前位置起的连续 KK 个元素翻转(若不够 KK 个则说明无法将数组变为全 1 的,返回 -1),下面给出正确性证明:

  1. 每个翻转 A[i:i+K1]A[i: i+K-1] 由它的左端点下标 ii 唯一确定,我们定义变量 fif_ii=0,1,,nKi=0, 1, \cdots, n-K,为翻转 A[i:i+K1]A[i: i+K-1] 的次数。
  2. 对任意一个可行方案,任意调整翻转的次序得到的方案仍然可行。这是因为决定了每个 A[i]A[i] 最终取值的仅有 A[i]A[i] 的初始值以及包含了 A[i]A[i] 的翻转的个数(的奇偶性),与翻转次序无关。
  3. 如果存在可行方案(存在可行方案意味着最优方案一定存在),则在最优方案(即包含的翻转个数最少的方案)中(记为 MM),每个翻转至多出现 1 次。这是因为如果 MM 中某个翻转的个数多于一个,则我们从 MM 去掉 2 个这个翻转得到的方案 MM' 同样是可行的,并且 M<M|M'|<|M|,矛盾。
  4. 作为上一条的推论,我们知道:最优方案中每个 fif_i 仅能取 0 或 1。
  5. i0i_{0} 为(原始)数组 AA 中从左到右第一个 0 的下标,我们证明:如果存在可行方案,则必存在最优方案 MMMMfi0=1f_{i_{0}}=1。若最优方案 MMfi0=0f_{i_{0}}=0,则必存在 jjmax(0,i0K+1)j<i0max(0,i_0-K+1)\leqslant j<i_0 使得 fj=1f_{j}=1。记方案 MM' 为:fi0=1f'_{i_{0}}=1fj=0f'_{j}=0,其余翻转与 MM 相同,则 MM' 一定也可行(从而也是最优的):比较数组 A1A_1 = AA + (fi0=1f'_{i_{0}}=1) + (fj=0f'_{j}=0) 与 A2A_2 = AA + (fi0=0f_{i_{0}}=0) + (fj=1f_{j}=1),显然 A1[0:j1]=A2[0:j1]A_1[0: j-1]=A_2[0: j-1]A1[i0+1: ]=A2[i0+1: ]A_1[i_0+1:\ ]=A_2[i_0+1:\ ],但 A1[j:i0]A_1[j: i_0] 全为 1,A2[j:i0]A_2[j: i_0] 至少包含一个 0(A2[j]=0A_2[j]=0)。
  6. 结合以上性质,对首个 0 元下标进行归纳,便可知:若存在可行方案,则这样给出的方案必是最优的。
  7. 最后证明:在没有可行方案时,此贪心策略能正确返回 -1。对 AA 按此贪心策略翻转之后,A[0:nK]A[0: n-K] 一定是全 1 的,则:存在可行方案 <=> 对 AA 按此贪心策略翻转之后,A[nK+1: ]A[n-K+1:\ ]全为 1。得证。

代码

class Solution {//贪心地从左到右依次翻转
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n=A.size(),ans=0;
        queue<int> q;
        for(int i=0;i<n;++i){
            if(!q.empty()&&i-q.front()>=K) q.pop();//维护与当前位置的距离<=K的翻转位置(左端点)
            if((A[i]+q.size())%2==0){              //需要翻转
                if(i+K>n) return -1;               //无法翻转
                q.push(i);
                ++ans;
            }
        }
        return ans;
    }
};

最后,点这里查看完整题解

共 0 个回复
暂无回复