描述:小紅想買些珠子做一串自己喜歡的珠串。賣珠子的攤主有很多串五顏六色的珠串,但是不肯把任何一串拆散了賣。於是小紅要你幫忙判斷一下,某串珠子裡是否包含了全部自己想要的珠子?如果是,那麼告訴她有多少多余的珠子;如果不是,那麼告訴她缺了多少珠子。
為方便起見,我們用[0-9]、[a-z]、[A-Z]范圍內的字符來表示顏色。例如在圖1中,第3串是小紅想做的珠串;那麼第1串可以買,因為包含了全部她想要的珠子,還多了8顆不需要的珠子;第2串不能買,因為沒有黑色珠子,並且少了一顆紅色的珠子。
輸入:每個輸入包含1個測試用例。每個測試用例分別在2行中先後給出攤主的珠串和小紅想做的珠串,兩串都不超過1000個珠子。
輸出:如果可以買,則在一行中輸出“Yes”以及有多少多余的珠子;如果不可以買,則在一行中輸出“No”以及缺了多少珠子。其間以1個空格分隔。
input:ppRYYGrrYBR2258
YrR8RrY
output:Yes 8
分析:這道題的難點在於每串珠子可能有多個相同顏色的,你需要判斷相同顏色數目的多少。
解決方法用一個數組來將每種顏色珠子的數目存起來,然後比較。
1 #include<iostream> 2 #include<string> 3 using namespace std; 4 5 void count(string a, int num[]) //將不同顏色珠子的數目存在數組中 6 { 7 for (int i = 0; i < a.size(); i++) 8 { 9 if (a[i] >= '0'&&a[i] <= '9') 10 num[a[i] - '0']++; 11 else if (a[i] >= 'a'&&a[i] <= 'z') 12 num[a[i] - 'a' + 10]++; 13 else 14 num[a[i] - 'A' + 35]++; 15 } 16 } 17 int main() 18 { 19 string a, b; 20 static int nA[62], nB[62]; 21 cin >> a >> b; 22 count(a, nA); 23 count(b, nB); 24 int n = 0; //缺少的珠子數目用n記下來,最後如果n=0,說明不缺少,可以買 25 for (int i = 0; i < 62; i++) 26 { 27 if (nB[i] == 0) 28 continue; 29 if (nB[i]>nA[i]) 30 n += nB[i] - nA[i]; 31 } 32 if (n == 0) 33 cout << "Yes" << " " << a.size() - b.size(); 34 else 35 cout << "No" << " " << n<<endl; 36 system("pause"); 37 return 0; 38 }