题目描述

小X正在指挥M个机器人做一道家常菜：白灼青菜。把一根青菜烧成菜肴需要两个步骤：洗菜和水煮。显然，一根青菜不可能同时被清洗和水煮，也不可能先被水煮后被清洗。

现在小X告诉你他是怎么指挥的。每当一个机器人空下来：

·如果有青菜还没被清洗，就让这个机器人清洗这根青菜

·否则如果有青菜还没被水煮，就让这个机器人水煮这根青菜

·都没有就让这个机器人关机

现在一共需要把N根青菜烧成菜肴，任何一个机器人清洗都要花A分钟，水煮要花B分钟。小X想请你告诉他多少分钟后所有菜能被烧好。

输入

第一行4个正整数N,M,A,B，含义见问题描述。

输出

输出1行包含一个整数，表示多少分钟后所有菜能被烧好。

样例输入

3 2 9 5样例输出

23提示

样例1解释

为了方便说明，把机器人标号为1号机器人和2号机器人；把青菜标号为1号、2号、

3号青菜。实际上，机器人间是没有区别的，青菜间也是没有区别的。

第分钟，1号机器人开始洗1号青菜，2号机器人开始洗2号青菜。

第9分钟，1号机器人开始洗3号青菜，2号机器人开始煮1号青菜。

第14分钟，2号机器人开始煮2号青菜。

第18分钟，1号机器人开始煮3号青菜。

第19分钟，2号机器人关机。

第23分钟，所有菜都被烧好了，1号机器人关机。

数据范围

本题共有 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，即两个步骤需要的时间相同

【分析】经分析数据范围可知，总时长最多为2×1000×（2×1000＋2×1000）=8×10^6，可以直接模拟。可以使用两个数组分别保存∶

● 在i时刻有多少台机器人变为空闲状态。

● 在i时刻有多少根菜被清洗完毕，变为"待水煮"状态。另外，保存当前"待清洗"和"待水煮"的菜的根数。

枚举当前时刻i，每次先更新当前"待水煮"的菜的个数，再使用当前空闲的机器人去清洗或水煮剩余的菜即可

参考程序：

关键词： 2021年常州市程序设计小能手烧菜cook cpp题解