Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

You are given two non-empty strings S and T of equal lengths. S contains the characters `0', `1' and `?', whereas T contains `0' and `1' only. Your task is to convert S into T in minimum number of moves. In each move, you can

1. change a `0' in S to `1'
2. change a `?' in S to `0' or `1'
3. swap any two characters in S

As an example, suppose S = "01??00" and T = "001010". We can transform S into T in 3 moves:

• Initially S = "01??00"
• - Move 1: change S[2] to `1'. S becomes "011?00"
• - Move 2: change S[3] to `0'. S becomes "011000"
• - Move 3: swap S[1] with S[4]. S becomes "001010"
• S is now equal to T

Input 

The first line of input is an integer C (C200) that indicates the number of test cases. Each case consists of two lines. The first line is the string S consisting of `0', `1' and `?'. The second line is the string T consisting of `0' and `1'. The lengths of the strings won't be larger than 100.

Output 

For each case, output the case number first followed by the minimum number of moves required to convert S into T. If the transition is impossible,output `-1' instead.

Sample Input 

3
01??00
001010
01
10
110001
000000

Sample Output 

Case 1: 3
Case 2: 1
Case 3: -1

---

題目描述：

操作有三:
1. 將 0 轉換成 1
2. 將 ? 轉換成 0 或 1
3. 任意對調兩個位置上的字元

給起始字串，求轉換到目標字串的最少次數。

題目解法：

由於可以任意對調兩個位置上的字元，因此可以猜測出是一道 greedy。

操作中不存在將 1 轉換成 0，因此只要保證 0 + ? 的個數可以大於等於目標字串的 0 的個數。

肯定存在解。

1. 先 greedy 操作 2，盡可能放置與目標字串相同的字元。
2. 再 greedy 操作 1，盡可能將 0 轉換成 1 後與目標字串相同。
3. 此時已經確保目標與起始字串的 0 和 1 個數相同了，接著檢查位置不同的個數，個數/2 即操作 3 的次數。

#include <stdio.h> 
#include <string.h> 

int main() {
	int testcase, cases = 0;
	int i, j, k;
	char S[105], T[105];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%s %s", &S, &T);
		printf("Case %d: ", ++cases);
		int tone = 0, tzero = 0;
		int sone = 0, szero = 0, snone = 0;
		int serr = 0, step = 0;
		for(i = 0; T[i]; i++) {
			if(T[i] == '0')	tzero++;
			else			tone++;
		}
		for(i = 0; S[i]; i++) {
			if(S[i] == '0')
				szero++;
			else if(S[i] == '1') 
				sone++;
			else
				snone++;
		}
		if(szero+snone < tzero) {
			puts("-1");
			continue;
		}
		for(i = 0; S[i]; i++) {
			if(S[i] == '?') {
				step++;
				if(T[i] == '0' && szero < tzero)
					S[i] = '0', szero++;
				else if(T[i] == '1' && sone < tone)
					S[i] = '1', sone++;
				else if(szero < tzero)
					S[i] = '0', szero++;
				else
					S[i] = '1', sone++;
			}
		}
		for(i = 0; S[i]; i++) {
			if(sone < tone && S[i] == '0' && T[i] == '1')
				sone++, szero--, step++, S[i] = '1';
		}
		for(i = 0; S[i]; i++)
			serr += S[i] != T[i];
		printf("%d\n", serr/2+step);
	} 
	return 0;
}