11308: Bankrupt Baker ★★☆☆☆ 題組：Problem Set Archive with Online Judge 解題者：陳子傑 解題日期：2017年3月30日 題意：有一個烘焙師要做蛋糕,因此有做蛋糕的食譜(1 ≦ t ≦100),食譜有蛋糕名稱,材料數量(m),蛋糕部位數量(n),預算金額(b)(1 ≦ m; n ≦ 100, 1 ≦ b ≦ 106),材料名稱,材料單價(0 ≦ c ≦ 5000),以及蛋糕各部位名稱,各部位所需的材料名稱及數量(1 ≦ k ≦ 100),現在我們要寫一程式把以上資料依序輸入並評估做這個蛋糕有多少部位是在預算內或者是成本太高,顯示太貴(Too expensive!)。

題意範例： Sample Input: gold 4500 2 Scrumptious Caramel Topping diamond 5000 Display Cake - Do Not Eat! 3 costlyflour 100 gold 100 diamond 100 2 My Favourite Cheesecake 8 3 100 sugar 4 water 0 lemonjuice 3 creamcheese 20 vanilla 5 egg 5 cream 10 strawberry 5 Strawberry Whipped Cream cream 5 strawberry 3 Scrumptious Caramel Topping 3 sugar 6 water 3 lemonjuice 1 Secret Cheesecake Base 5 creamcheese 3 sugar 5 vanilla 1 egg 6 cream 1 Million Dollar Cakes 3 1 999999 costlyflour 500

/*1. 蛋糕名稱要轉大寫 2. 蛋糕部位名稱要依成本低到高依序印出 3. 蛋糕部位名稱要依字母順序依序印出 4. 每個蛋糕之間要空行*/ 題意範例： Sample Output: MY FAVOURITE CHEESECAKE Scrumptious Caramel Topping Strawberry Whipped Cream MILLION DOLLAR CAKES Too expensive! /*1. 蛋糕名稱要轉大寫 2. 蛋糕部位名稱要依成本低到高依序印出 3. 蛋糕部位名稱要依字母順序依序印出 4. 每個蛋糕之間要空行*/

解法： 先輸入所需評估蛋糕數量,並產生一個迴圈 每個迴圈中需要一個map做材料單價表,以利搜尋和累加成本,以及一個自定義的結構(struct)Recipe陣列 這個Recipe結構儲存每個蛋糕部位的名稱和成本以及重載(Overloading)” < “ 之所以要重載” < ”是因為題目有要求蛋糕部位名稱要依成本低到高依序印出,所以Recipe陣列收集完後要做排序,這裡採用#include <algorithm>的sort()函式,由於要排序結構,所以當然就要重載囉 建構材料單價表需要一個迴圈 收集蛋糕各部位的資料需要兩個迴圈,一個是蛋糕部位的迴圈,另一個是個蛋糕部位中的成本累加的迴圈 排序完後,依照先前說的規則印出,若每個蛋糕中第一個蛋糕部位就超過成本,直接印出” Too expensive!”,後面不用印,若無則印到成本超過預算的部位結束(超過者不印) 最後記得還要再印一個空行喔

struct Recipe{ //蛋糕部位名稱與成本 解法範例： struct Recipe{ //蛋糕部位名稱與成本 string name; int cost; bool operator <(const Recipe& t) const{ if(cost!=t.cost) return cost<t.cost; else return name<t.name; } }; //用map收集材料和價格 map<string, int> ingredient;//材料價格表 for(int j=0; j<m; j++){ cin>>tmp>>c; getchar(); ingredient[tmp]=c;

for(int j=0; j<n; j++){ //蛋糕每一部位所需的材料數量 getline(cin, tmp); cin>>k; getchar(); recipe[j].name=tmp; recipe[j].cost=0; for(int l=0; l<k; l++){ //計算每一蛋糕部位的成本 int x; cin>>tmp>>x; iter=ingredient.find(tmp); //從材料表去找單價計算成本 if(iter!=ingredient.end()) recipe[j].cost=recipe[j].cost+iter->second*x; else cout<<"The ingredient doesn't exist!"<<endl; }

//蛋糕名稱 cout<<title<<endl; //蛋糕部位 //先排序因為成本要由低印到高 sort(recipe, recipe+n);//sort(陣列排序開頭,陣列排序尾巴) int first=0; for(int j=0; j<n; j++){ if(recipe[j].cost>b&&first==0){ cout<<"Too expensive!"<<endl; break; } if(recipe[j].cost<=b){ cout<<recipe[j].name<<endl; first=1; cout<<endl;//題目要求每個binder都要一個空行

討論 關於struct的重載為何是用小於而不是大於呢? 這是因為在std::sort的巨集(一系列預定義的規則取代一定的文字模式)中之定義是如此: struct _Iter_less_iter { template<typename _Iterator1, typename _Iterator2> bool operator()(_Iterator1 __it1, _Iterator2 __it2) const{ return *__it1 < *__it2; } }; 關於字母順序的排序是用string重載的”<”來達成,以ASCII的數字大小為原則,若字首一樣則以長度來比較