首页 > 代码库 > UVA - 12545 Bits Equalizer (比特变换器)(贪心)
UVA - 12545 Bits Equalizer (比特变换器)(贪心)
题意:输入两个等长(长度不超过100)的串S和T,其中S包含字符0,1,?,但T只包含0和1,你的任务是用尽量少的步数把S变成T。有以下3种操作:
1、把S中的0变成1。
2、把S中的“?”变成0或1。
3、交换S中任意两个字符。
分析:
1、为保证步数最少,先统计两串中1的个数和1的位置。如果cnta>cntb,则不能把S变成T,因为1不能变成0。
2、先将?变成0或1,变换原则是若cnta<cntb且b中对应位置为1,则变为1;否则,变为0。
3、再将0变成1,变换原则是cnta<cntb且b中对应位置为1。
4、此时两串1的个数相同。
5、再枚举a中1的位置,如果相同位置b中也有,则说明,这个位置无需变换,否则b中必有一个可与当前位置交换的1。
#pragma comment(linker, "/STACK:102400000, 102400000") #include<cstdio> #include<cstring> #include<cstdlib> #include<cctype> #include<cmath> #include<iostream> #include<sstream> #include<iterator> #include<algorithm> #include<string> #include<vector> #include<set> #include<map> #include<stack> #include<deque> #include<queue> #include<list> #define Min(a, b) ((a < b) ? a : b) #define Max(a, b) ((a < b) ? b : a) typedef long long LL; typedef unsigned long long ULL; const int INT_INF = 0x3f3f3f3f; const int INT_M_INF = 0x7f7f7f7f; const LL LL_INF = 0x3f3f3f3f3f3f3f3f; const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f; const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1}; const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1}; const int MOD = 1e9 + 7; const double pi = acos(-1.0); const double eps = 1e-8; const int MAXN = 100 + 10; const int MAXT = 10000 + 10; using namespace std; char a[MAXN]; char b[MAXN]; vector<int> va, vb;//记录字符串a,b中1的位置 int main(){ int T; scanf("%d", &T); int kase = 0; while(T--){ scanf("%s%s", a, b); va.clear(); vb.clear(); int ans = 0; int len = strlen(a); int cnta = 0, cntb = 0;//字符串a,b中1的个数 for(int i = 0; i < len; ++i){ if(a[i] == ‘1‘){ ++cnta; va.push_back(i); } if(b[i] == ‘1‘){ ++cntb; vb.push_back(i); } } for(int i = 0; i < len; ++i){//修改a中的? if(a[i] == ‘?‘){ ++ans; if(cnta < cntb && b[i] == ‘1‘){ a[i] = ‘1‘; va.push_back(i); ++cnta; } else{ a[i] = ‘0‘; } } } for(int i = 0; i < len; ++i){//修改a中的0 if(a[i] == ‘0‘ && b[i] == ‘1‘ && cnta < cntb){ ++cnta; a[i] = ‘1‘; ++ans; va.push_back(i); } } int lena = va.size(); int lenb = vb.size(); for(int i = 0; i < lena; ++i){//统计需要交换的1的个数 bool ok = false; for(int j = 0; j < lenb; ++j){ if(va[i] == vb[j]){ ok = true; break; } } if(!ok) ++ans; } printf("Case %d: ", ++kase); if(cnta > cntb){ printf("-1\n"); } else{ printf("%d\n", ans); } } return 0; }
UVA - 12545 Bits Equalizer (比特变换器)(贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。