我在测试一些网站时遇到了以下问题:
John and Mary founded J&M publishing house and bought two old printers to equip it. Now they have their first commercial deal - to print a document consisting of N pages. It appears that printers work at different speed. One produces a page in X seconds and other does it in Y seconds. So now company founders are curious about minimum time they can spend on printing the whole document with two printers.
(取自此处http://codeabbey.com/index/task_view/two-printers)
我以为是贪心算法的问题，但据说N可以达到十亿，所以也许有一些我看不到的更简单的解决方案。我能以某种方式解决将它们按 X 和 Y 的比例划分的问题吗？
最佳答案
这似乎是一道数学题而不是算法题。作业分配为 YN/(X+Y) 页到 X，XN/(X+Y) 页到 Y 。总时间为 XYN/(X+Y)，这是最优的(请注意，它等效于 N/(1/X + 1/Y)。因为 YN/(X+Y) 可能不是整数，你可以只计算一些值(如果 X 向上舍入而 Y 向下舍入，反之亦然)，然后取最小值。或者如您所说，您可以将两者四舍五入并将任何剩余的工作交给速度更快的机器。
关于由两个执行者共享作业的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19176589/