这道题是一道数学分析/归纳题目。
一个比较直观的结论是如果一个机器人要建造另一个机器人,那么应该尽早(在开始执行任务之前)建造。这样被建造的机器人可以更早开始干活。
所以整个过程大概是一开始所有机器人都在倍增,总数量1->2->4->8...->2^k,直到某个临界值2^k。
然后大家可能会纠结,这2^k个机器人会不会一部分比如说X个又造了一波机器人然后开始执行任务,而其余Y个直接开始执行任务。
事实上经过分析可以发现不会出现上述情况,这2^k个机器人要不都再倍增一波,要不都去执行任务直到N个任务都完成。
(一个简单的分析思路是,可以比较X个机器人平均完成的任务数于Y个机器人平均完成的任务数谁高,X高就应该全部倍增,Y高就应该全部执行任务)
这样我们就有了一个log(N)的算法,枚举每一个k,然后计算倍增到2^k再全部执行任务需要用的时间,为kq + ceil(n / (2^k))。
其实我们还可以进一步分析。如果一个机器人的总执行任务的时间超过2q的话,那么对这个机器人来说,显然不如花q时间再造一个机器人,然后2个机器人一起执行任务。
换句话说,每个机器人执行任务的时间都不超过2q。所以我们可以直接求出k = ceil(log2(n / 2q))