首页 > 代码库 > UVA12545(比特转换器)。

UVA12545(比特转换器)。

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

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn = 100+10;
 5 int main()
 6 {
 7     char s[maxn],t[maxn];
 8     int x,i,j,kase = 0;
 9     cin >> x;
10     while(x--)
11     {
12         int sum = 0,p = 0,cnt1 = 0,cnt2 = 0;
13         scanf("%s%s",s,t);
14         int len = strlen(s);
15         for(i=0; i<len; i++)
16         {
17             if(s[i]==?)
18                 p++;
19             if(s[i] == 1&&t[i]==0)
20                 cnt1++;
21             else if(t[i]==1&&s[i]!=1)
22                 cnt2++;
23         }
24         if(cnt1>cnt2)
25         {
26             printf("Case %d: -1\n",++kase);
27             continue;
28         }
29         sum+=p;
30         int exchange = 0,other = 0;
31         for(i=0; i<len; i++)
32         {
33             if(s[i] == 1&&t[i]==0)
34                 exchange++;
35             else if(s[i]==0&&t[i]==1)
36                 other++;
37         }
38         sum += max(exchange,other);
39         printf("Case %d: %d\n",++kase,sum);
40     }
41     return 0;
42 }

 

UVA12545(比特转换器)。