hiho一下第256周《Diligent Robots》题目分析

2
1

这道题是一道数学分析/归纳题目。

一个比较直观的结论是如果一个机器人要建造另一个机器人,那么应该尽早(在开始执行任务之前)建造。这样被建造的机器人可以更早开始干活。

所以整个过程大概是一开始所有机器人都在倍增,总数量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))

0 answer(s)

write answer 切换为英文 切换为中文


转发分享