8-3 Bits Equalizer uva12545

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：

给出字符串s包含'0' '1' '?';

再给出字符串ｔ只包含０１；

现在我们可以对Ｓ做三个操作；把０变成１，把？变成０或１，任意两个位置交换；

问最少操作几次ｓ　＝＝　ｔ；

贪心默认除去那些已经相同的然后收集四种信息

共有三种不同的情况直接模拟即可

#include<bits/stdc++.h>

using namespace std;

#define N 200000+5

int main()

{

    int n;cin>>n;

    char a[N],b[N];

    for(int kase=;kase<=n;kase++)

    {

        int c=;

        int one,zero;//代表a和b不同时 a为什么

        int ask_one,ask_zero;//代表问号下面是几

        one=zero=ask_one=ask_zero=;

        scanf("%s%s",a,b);

        for(int i=;i<strlen(a);i++)

        {

            if(a[i]==b[i])continue;

            if(a[i]==''&&b[i]=='')one++;

            if(a[i]==''&&b[i]=='')zero++;

            if(a[i]=='?')

            {

                if(b[i]=='')ask_zero++;

                else   ask_one++;

            }

        }

        if(zero>=one)

            c=zero+ask_one+ask_zero;

        else

        {

            if(one-zero>ask_one){c=-;}

            else

             c+= ask_one+ask_zero+one;

        }

        printf("Case %d: %d\n",kase,c);

    }

    return ;

}