这个贪心算法的代码如何理解改a[i]=0并改变这个a[i+j]的值？

Question

对于10的情况，为什么 要使用一个变量j，代表离当前位的距离，初始值为2 ，从当前位的下一位开始，逐个向后遍历，直到找到一个和j的奇偶性不同的数字。
为什么要找到一个和j的奇偶性不同的数字呢？
如何理解改a[i]=0并改变这个a[i+j]的值？
链接：https://ac.nowcoder.com/acm/contest/76536/A
来源：牛客网

题目描述
有一个长度为 N 仅由 0 和 1 组成的字符串 S，你可以进行若干次如下操作（也可以是 0 次）：

选择两个相邻的 1 全变成 0 或者选择两个相邻的 0 全变成 1

求将字符串 S 的每一位都变成 0 所需的最小操作次数。
输入描述:
第一行输入一个正整数
T(1≤T≤2×10的五次方)，表示数据组数。

接下来输入 2T 行，每组数据两行，先输入一行一个正整数 N(1≤N≤2×10的五次方）表示字符串 S 的长度，接下来输入一行字符串S（仅包含 0和1）

数据保证N 的总和不超过 2×10的五次方

输出描述:
输出 T 行，对于每组数据，输出一行一个整数表示将字符串 S 的每一位都变成 0 所需的最小操作次数（如果不能实现输出 −1

输入
3
2
00
3
101
4
1001

输出
0
-1
3

#include<bits/stdc++.h>
using namespace std;
 
int T,n,res,a[300000];
bool f;
 
int main(){
    cin>>T;
    while (T--){
        scanf("%d",&n);
        res=0; f=true;
        for (int i=1;i<=n;i++) scanf("%1d",&a[i]);
        for (int i=1;i<=n-1;i++){
            if (a[i]==1 and a[i+1]==1){
                a[i]=a[i+1]=0;
                res++;
            }
            else if (a[i]==1 and a[i+1]==0){
                a[i]=0; res++;
                for (int j=2;j<=n-i+1;j++){
                    if (j==n-i+1){
                        f=false;
                        break;
                    }
                    res++;
                    if (a[i+j]==j%2){
                        a[i+j]=1-j%2;
                        break;
                    }
                }
            }
        }
        if (a[n]==1) f=false;
        if (!f) printf("-1\n");
            else printf("%d\n",res);
    }
    return 0;
}
 

Answer 1

引自免费微信小程序：皆我百晓生

在给定的贪心算法代码中，该问题的目标是计算将一个仅包含0和1的字符串S中的所有位都变为0所需的最小操作次数。每次操作可以将两个相邻的相同数字（0或1）翻转为相反的数字。

对于a[i]=0并改变a[i+j]值的部分，这是在处理特殊情况时进行的操作。当遇到连续的"10"时（即a[i]==1且a[i+1]==0），首先将a[i]置零，并增加操作计数器res。然后，从当前位置i的下一个位置开始向后查找（即从i+2开始），试图找到一个与当前遍历距离j的奇偶性不同的数字。例如，如果j是偶数，那么我们寻找的是一个1，因为1对应于奇数位置；如果j是奇数，则寻找0。

以下是这段逻辑对应的代码片段：

if (a[i]==1 and a[i+1]==0){
    a[i]=0; res++;
    for (int j=2;j<=n-i+1;j++){
        if (j==n-i+1){
            f=false;
            break;
        }
        res++;
        if (a[i+j]==j%2){
            a[i+j]=1-j%2;
            break;
        }
    }
}

这个循环的目的是通过最少的操作次数来确保当前位置i之后的某个位置能够被转换为1（如果j是偶数）或0（如果j是奇数），从而维持一种平衡，使得后续可以通过更少的操作将剩余的所有位都变为0。

然而，需要注意的是，根据题目描述，这种贪心策略并不保证能得到全局最优解。实际解决此题目的正确方法应该是采用动态规划，而非贪心算法。由于给出的代码采用贪心策略，因此可能无法正确解决某些测试用例，这也是为什么输出部分有检查标志变量f并在不能实现时输出-1的原因。对于原题目的正确解答，请参考使用动态规划的方法。