2010年1月7日星期四.sgu170
sgu170:
簡(jiǎn)單題。
題意很簡(jiǎn)單，就是求兩個(gè)只有+-組成的字符串，通過(guò)互換相鄰的兩個(gè)+-，是否能夠由第一個(gè)串，變成第二個(gè)，給出最短的變換步數(shù)。
直覺(jué)的想法：廣搜
這樣顯然有問(wèn)題，字符串長(zhǎng)5000，怎么搜復(fù)雜度都太高。
猜想:貪心
對(duì)于兩個(gè)字符串a(chǎn)，b，相同的兩個(gè)區(qū)間，如果a[s....t] 和
b[s...t]所含的+-數(shù)量一樣多，那么由a[s...t] 到 b[s...t]
的最小距離一定是其中減號(hào)或者加號(hào)的差的絕對(duì)值的和
比如:
-+-+-
到
---++
最小步數(shù)就是0 + 1 + 2 = 3
本題就直接求兩個(gè)串的符號(hào)差即可
1 http://m.shnenglu.com/schindlerlee
2 bool judge()
3 {
4 len1 = strlen(stra);
5 len2 = strlen(strb);
6 if(len1 != len2) return false;
7 int i,res = 0;
8 for(i = 0;i < len1;i++) {
9 if(stra[i] == '-') { out1[top1++] = i; }
10 if(strb[i] == '-') { out2[top2++] = i; }
11 }
12 if(top1 != top2) return false;
13 for(i = 0;i < top1;i++) {
14 res += abs(out1[i] - out2[i]);
15 }
16 printf("%d\n",res);
17 return true;
18 }
19
20