习题 8-3 比特变换器（Bits Equalizer, SWERC 2012, UVa12545）

本文主要是介绍习题 8-3 比特变换器（Bits Equalizer, SWERC 2012, UVa12545），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://vjudge.net/problem/UVA-12545
分类：贪心法
备注：简单思维题

先看还少多少个’1’，如果s的’1’多余t的‘1’肯定无解。
然后把少掉的这些’1’，全部用’?‘去变成’1’，如果’?‘有剩余则变“0‘。
如果’?‘不够，则要把遍历一遍，当’1’的数量处于不足状态时，把没匹配的’0’变’1’。
最后会剩下2*k个位置不匹配的字符，两两交换，贡献为k。

#include<bits/stdc++.h>
using namespace std;
const int maxn=105;
int n;
char s[maxn],t[maxn];
int main(void){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s%s",s,t);printf("Case %d: ",i);int len=strlen(s),num=0,cnt=0;//num求还少几个'1'for(int i=0;i<len;i++){if(s[i]=='?')cnt++;if(s[i]=='1')num--;if(t[i]=='1')num++;}cnt-=num;if(num<0){printf("-1\n");continue;}int ans=0,num2=0;for(int i=0;i<len;i++){if(s[i]=='?'){ans++;if(t[i]=='1'){if(num)s[i]='1',num--;else s[i]='0',cnt--;}else{if(cnt)s[i]='0',cnt--;else s[i]='1',num--;}}}for(int i=0;i<len;i++){if(s[i]!=t[i]){if(s[i]=='0'&&num)s[i]='1',ans++,num--;else s[i]='1',num2++;}}printf("%d\n",ans+num2/2);}return 0;
}

这篇关于习题 8-3 比特变换器（Bits Equalizer, SWERC 2012, UVa12545）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---