UVA12545_Bits Equalizer

题目意思很简单，给你两个串，第一个串为0,1或者？，第二个串为0，1，

每次你可以对第一个串进行三种操作，1、0变为1；2、？变为0或者1；3、交换任意两个数的位置。

现在问你能否把第一个串变为第一个串？最少的步数是多少呢？？

其实关键抓住一点：0可以变1,1不能变0。

然后剩下的就是简单的贪心了。

#include <iostream>

#include <cstring>

#include <cstdio>

#define maxn 122

using namespace std;

char s1[maxn],s2[maxn];

int n,m,l,t,z1,z2,o1,o2,ans,cas=,tep;

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        scanf("%s",s1+);

        scanf("%s",s2+);

        printf("Case %d: ",++cas);

        l=strlen(s1+);

        ans=o1=o2=z1=z2=;

        for (int i=; s1[i]; i++)

        {

            if (s1[i]=='') z1++;

            if (s1[i]=='') o1++;

            if (s2[i]=='') z2++;

            if (s2[i]=='') o2++;

        }

        if (z1>z2)

        {

            printf("-1\n");

            continue;

        }

        for (int i=; s1[i]; i++)

        {

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

            {

                if (s2[i]=='' && z1<z2)

                {

                    s1[i]='';

                    z1++;

                    ans++;

                }

            }

        }

        for (int i=; s1[i]; i++)

        {

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

            {

                if (s2[i]=='' && o1<o2)

                {

                    s1[i]='';

                    o1++;

                    ans++;

                }

            }

        }

        for (int i=; s1[i]; i++)

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

            {

                if (s2[i]=='') s1[i]='',o1++;

                else s1[i]='',z1++;

                ans++;

            }

        for (int i=; s1[i]; i++)

        {

            if (z1<z2 && s1[i]=='' && s2[i]=='')

            {

                ans++;

                s1[i]='';

                z1++,o1--;

            }

        }

        tep=;

        for (int i=; s1[i]; i++)

            if (s1[i]!=s2[i]) tep++;

        if (tep&)

        {

            printf("-1\n");

            continue;

        }

        ans+=(tep>>);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

UVA12545_Bits Equalizer

最新文章

热门文章