论坛 › Exchange › UVA12545(比特转换器)。

pengjunling 发表于 2017-7-2 15:06:05

UVA12545(比特转换器)。

　　贪心的思想，如果S串是1而t串是0，只能够交换。除去相同的部分，如果上面的1比下面的1多，就无法变换成功，输出-1.



#include <bits/stdc++.h>
using namespace std;
const int maxn = 100+10;
int main()
{
   char s,t;
   int x,i,j,kase = 0;
   cin >> x;
   while(x--)
   {
         int sum = 0,p = 0,cnt1 = 0,cnt2 = 0;
         scanf("%s%s",s,t);
         int len = strlen(s);
         for(i=0; i<len; i++)
         {
             if(s=='?')
               p++;
             if(s == '1'&&t=='0')
               cnt1++;
             else if(t=='1'&&s!='1')
               cnt2++;
         }
         if(cnt1>cnt2)
         {
             printf("Case %d: -1\n",++kase);
             continue;
         }
         sum+=p;
         int exchange = 0,other = 0;
         for(i=0; i<len; i++)
         {
             if(s == '1'&&t=='0')
               exchange++;
             else if(s=='0'&&t=='1')
               other++;
         }
         sum += max(exchange,other);
         printf("Case %d: %d\n",++kase,sum);
   }
   return 0;
}

查看完整版本: UVA12545(比特转换器)。