UVa 12545 Bits Equalizer【贪心】

题意：给出两个等长的字符串，0可以变成1，?可以变成0和1，可以任意交换s中任意两个字符的位置，问从s变成t至少需要多少次操作

先可以画个草图

发现需要考虑的就是

1---0

0---1

?---0

?---1

下面三种都是只需要一次操作就可以完成的，

所以应该优先考虑1---0

如果存在0---1,就优先交换1---0和0---1，因为这样可以同时满足两组

如果不存在0---1,就交换1---0与?---1,这样每交换一次，需要两次操作，即先将问号变成0,再交换

如果最后都还剩下有1--0（因为下面的0是动不了的，无法再配对了），说明上面的1找不到与它配对的了，不存在

自己写的挫爆了（而且还是错的----）---网上看了好几篇题解的贪心也好繁琐

学习的这一篇 http://acm.lilingfei.com/uva-12545-bits-equalizer-%E4%B9%A0%E9%A2%988-3_98

好棒o(≧v≦)o~~

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 char s[maxn];

 char t[maxn];

 int main(){

     int T;

     scanf("%d",&T);

     int kase=;

     while(T--){

         cin>>s;

         cin>>t;

         int len=strlen(s);

         int one_zero=,zero_one=,q_one=,q_zero=;

         for(int i=;i<len;i++){

             if(s[i]==''&&t[i]=='') one_zero++;

             if(s[i]==''&&t[i]=='') zero_one++;

             if(s[i]=='?'&&t[i]=='') q_one++;

             if(s[i]=='?'&&t[i]=='') q_zero++;

         }

         int ans=;

         while(one_zero&&zero_one){

             ans++;

             one_zero--;

             zero_one--;

         }

         while(one_zero&&q_one){

             ans+=;

             one_zero--;

             q_one--;

         }

         if(one_zero) ans=-;

         else ans+=zero_one+q_one+q_zero;

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

     }

     return ;

 }

巴特西

UVa 12545 Bits Equalizer【贪心】

最新文章

热门文章