CF1633B Minority题解

__vector__ · 2022-02-02 21:06:29 · 题解

题目大意：

给定一个数组。可以随便选一个子区间执行这样的操作：
一、如果这个子区间 0 和 1 的数量相同，不执行操作
二、如果这个子区间 0 和 1 的数量不同，若 0 的数量严格小于 1 ，那么删除子区间所有的 0 ，反之删除子区间所有的 1 。
求最多能删除的元素个数

题目解法：

第一眼看到，只能想到 O(n^2)的暴力（我太菜了）
再想想，可以发现可以贪心的选择整个数组执行操作。这样就能保证删除元素最多了。
如果 0 和 1 数量相等呢？只需要从区间头部或尾部随便删去一个元素就行了。

AC代码：

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
const int maxn=2e5+5;
char a[maxn];
int zero;
int one;
int ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        zero=one=0;
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='0')zero++;
            if(a[i]=='1')one++;
        }
        ans=min(zero,one);
        if(zero==one)ans--;
        printf("%d\n",ans);
    }
 //   system("pause");
    return 0;
}