Uva 12545 能从0变成1却不能轻易地从1变回0

一、题意

输入两个等长的字符串S、T，你的任务是用最少的操作步数把S变成T。
S由0、1、?构成，T由0、1构成。
可用的操作有：

• 把一个0变成1
• 把一个?变成0或1
• 交换两个字符的位置
  输出最少步数。若没有办法则输出-1.

二、解析

这里的操作最关键的就是1如何变成0。我们用 x->y 表示x需要变成y。
实际上只可能通过交换 1->0 和一个 0->1 得到。因为交换 1->0 和 0->0 就会使得被交换得数对变成 1->0 这相当于没有解决问题。

因此我们统计 1->0 和 0->1 得个数，分别记为one2zero、zero2one。

若zero2one不够，则通过 ?->1 来进行补充，若这样还不够，则无解。若足够，则 交换 1->0 和 0->1 （一部分由?->1得到），然后剩余的 ?->x 就直接转变为 x->x （x=0,1）即可。

若zero2one充足，则无需补充，只要记得把多余的 0->1 变为 1->1 即可。

三、代码

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int kase;

int main() {
    cin >> kase;
    for(int K = 1; K <= kase; K ++) {
        string a, b;
        cin >> a >> b;
        int one2zero = 0, zero2one = 0, none2one = 0, none2zero = 0;
        for(int i = 0; i < a.size(); i ++) if(a[i] != b[i]) {
            if(a[i] == '1') one2zero ++;
            else if(a[i] == '0') zero2one ++;
            else if(b[i] == '1') none2one ++;
            else none2zero ++;
        }
        int ans = none2one + none2zero;  // ?总是要转变的，无论是否作为zero2zero的补充
        if(zero2one + none2one >= one2zero) ans += max(one2zero, zero2one);
        else ans = -1;
        cout << "Case " << K << ": " << ans << endl;
    }
}

四、归纳

• 思考题题目时要会抓重点进行突破。