首页 > 其他 > 详细

UVA 12545 Bits Equalizer

时间:2015-12-17 22:16:22      阅读:194      评论:0      收藏:0      [点我收藏+]
技术分享
#include<bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define MS0(a) memset(a,0,sizeof(a))

using namespace std;

typedef long long ll;
const int maxn=1000100;
const int INF=1<<29;

char s[maxn],t[maxn];
int len;
int c10,c01,c1,c0;

int main()
{
    freopen("in.txt","r",stdin);
    int T;cin>>T;
    int casen=1;
    while(T--){
        scanf("%s%s",s,t);
        len=strlen(s);
        c10=c01=c1=c0=0;
        REP(i,0,len-1){
            if(s[i]==0&&t[i]==1) c01++;
            if(s[i]==1&&t[i]==0) c10++;
            if(s[i]==?&&t[i]==0) c0++;
            if(s[i]==?&&t[i]==1) c1++;
        }
        //cout<<c01<<" "<<c10<<" "<<c0<<" "<<c1<<endl;
        int ans=0;
        if(c01>=c10){
            ans+=c10;
            c01-=c10;
            ans+=c01+c1+c0;
        }
        else{
            ans+=c01;
            c10-=c01;
            if(c1>=c10){
                ans+=c10*2;
                c1-=c10;
                ans+=c1+c0;
            }
            else ans=-1;
        }
        printf("Case %d: %d\n",casen++,ans);
    }
    return 0;
}
View Code

贪心,分类讨论一下确定一下操作的优先顺序就好了。

UVA 12545 Bits Equalizer

原文:http://www.cnblogs.com/--560/p/5055342.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!