2021年常州市"程序設(shè)計小能手"《燒菜(cook.cpp)》題解

題目描述

小X正在指揮M個機器人做一道家常菜：白灼青菜。把一根青菜燒成菜肴需要兩個步驟：洗菜和水煮。顯然，一根青菜不可能同時被清洗和水煮，也不可能先被水煮后被清洗。

現(xiàn)在小X告訴你他是怎么指揮的。每當(dāng)一個機器人空下來：

·如果有青菜還沒被清洗，就讓這個機器人清洗這根青菜

·否則如果有青菜還沒被水煮，就讓這個機器人水煮這根青菜

·都沒有就讓這個機器人關(guān)機

現(xiàn)在一共需要把N根青菜燒成菜肴，任何一個機器人清洗都要花A分鐘，水煮要花B分鐘。小X想請你告訴他多少分鐘后所有菜能被燒好。

輸入

第一行4個正整數(shù)N,M,A,B，含義見問題描述。

輸出

輸出1行包含一個整數(shù)，表示多少分鐘后所有菜能被燒好。

樣例輸入

3 2 9 5樣例輸出

23提示

樣例1解釋

為了方便說明，把機器人標(biāo)號為1號機器人和2號機器人；把青菜標(biāo)號為1號、2號、

3號青菜。實際上，機器人間是沒有區(qū)別的，青菜間也是沒有區(qū)別的。

第分鐘，1號機器人開始洗1號青菜，2號機器人開始洗2號青菜。

第9分鐘，1號機器人開始洗3號青菜，2號機器人開始煮1號青菜。

第14分鐘，2號機器人開始煮2號青菜。

第18分鐘，1號機器人開始煮3號青菜。

第19分鐘，2號機器人關(guān)機。

第23分鐘，所有菜都被燒好了，1號機器人關(guān)機。

數(shù)據(jù)范圍

本題共有 20 個測試點，每個測試點 5 分。

對于測試點 1-10 ：1

對于測試點 11-20：1

對于測試點 1,2,11,12：M>N，即機器人比青菜多

對于測試點 3,4,13,14：M=1，即只有 1 個機器人

對于測試點 5,6,15,16：A=B，即兩個步驟需要的時間相同

【分析】經(jīng)分析數(shù)據(jù)范圍可知，總時長最多為2×1000×（2×1000＋2×1000）=8×10^6，可以直接模擬。可以使用兩個數(shù)組分別保存∶

● 在i時刻有多少臺機器人變?yōu)榭臻e狀態(tài)。

● 在i時刻有多少根菜被清洗完畢，變?yōu)?待水煮"狀態(tài)。另外，保存當(dāng)前"待清洗"和"待水煮"的菜的根數(shù)。

枚舉當(dāng)前時刻i，每次先更新當(dāng)前"待水煮"的菜的個數(shù)，再使用當(dāng)前空閑的機器人去清洗或水煮剩余的菜即可

參考程序：

關(guān)鍵詞： 2021年常州市程序設(shè)計小能手燒菜cook cpp題解