[普及+]零一子段详解

常规
1

我回来刷题解啦！~

题目评析

这是一道颇具综合性的前缀和+二分好题

题意分析

题目要求从一个01字符串中删除部分字符（可以从前后删，允许删空），使得以下两者中的较大的尽可能小：

  • 删除的 1 的个数
  • 留下的 0 的个数

对于每组数据，我们需要输出一个最小代价。

代码解析

1. 输入与初始化

int sum0[100001],sum1[100001];
char s[100001];

sum0[i] 和 sum1[i] 分别用来记录字符串中前 i 个字符中 0 和 1 的个数。s 存储输入的字符串。

2. 前缀和计算

for(int i=1;i<=len;i++){
    sum0[i]=sum0[i-1];
    sum1[i]=sum1[i-1];
    if(s[i]=='1'){
        sum1[i]+=1;
    }
    else{
        sum0[i]+=1;
    }
}

这段代码计算前缀和，sum1[i] 记录了从字符串的开始到第 i 个字符中 1 的个数，sum0[i] 记录了 0 的个数。这样，我们就可以快速得出任意子串中的 1 和 0 的个数，以便后面的二分查找。

3. 二分查找

int l=-1,r=len+1;
while(l+1<r){
    int mid=(l+r)/2;
    if(check(mid,len)){
        r=mid;
    }
    else{
        l=mid;
    }
}

这是一个典型的二分查找。我们要查找最小的 m，使得代价满足要求。l 和 r 是二分查找的左右边界，mid 是中间值。通过调用 check(mid, len) 来判断当前 m 是否可行。如果可行，就缩小右边界 r，否则缩小左边界 l。

4. check 函数

bool check(int m,int n){
    for(int x=n,y=n;x>=1;x--){
        while(sum0[x]-sum0[y-1]<=m&&y>0){
            y--;
        }
        if(sum1[y]-sum1[0]+sum1[n]-sum1[x]<=m){
            return 1;
        }
    }
    return 0;
}

check 函数判断给定的 m 是否能够满足条件：

  • sum0[x]-sum0[y-1]<=m 表示删除的 1 的个数。
  • sum1[y]-sum1[0]+sum1[n]-sum1[x]<=m 表示删除的 0 的个数。

如果在某种删除方案下，删除的 1 的个数和留下的 0 的个数的最大值不超过 m，则返回 1，表示 m 可行；否则返回 0。

5. 输出结果

cout<<r<<endl;

最终，r 即为满足条件的最小代价。

总体思路

这个题目利用了 二分查找 和 前缀和 来高效地计算最小代价。通过枚举每一种可能的删除方式，我们试图最小化代价，而二分查找帮助我们缩小了搜索的范围。检查每一个 m 是否可行的操作通过 check 函数来实现。

最后，各位大佬记得点赞:+1:！完结撒花

3 个赞
2

bool check(int m,int n){
for(int x=n,y=n;x>=1;x–){
while(sum0-sum0[y-1]<=m&&y>0){
y–;
}
if(sum1[y]-sum1[0]+sum1[n]-sum1<=m){
return 1;
}
}
return 0;
}
sum1[0]不是永远为0吗

1 个赞