算法由两个遗嘱执行人共享工作 [英] Algorithm for sharing jobs by two executors

问题描述

我遇到了以下问题，同时测试一些网站：

I encountered the following problem, while testing some web-site:

约翰和玛丽创办J＆放，M出版社买了两张旧打印机   装备吧。现在，他们有他们的第一个商业化的交易 - 打印   文件包括N个页面。看来，打印机在工作   不同的速度。一个产生页秒钟后和其他做它   Y秒。所以，现在公司的创始人是好奇最短的时间，他们   可以花印有两台打印机的整个文档。

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：//$c$cabbey.com/index/ task_view /两打印机）

我认为这是贪心算法问题，但被告知是n可能高达十亿，所以有可能是一些简单的解决方案，我都看不到。我会来解它们划分比例X和Y不知何故？

I thought it is the problem for greedy algorithm, but it is told that N could be up to billion, so there perhaps is some simpler solution which I could not see. Could I come to solution dividing them in proportion to X and Y somehow?

推荐答案

这似乎是一个数学问题，而不是算法的问题。这项工作分配将是 YN /（X + Y）页面 X ， XN / （X + Y）页面是。总时间将是 XYN /（X + Y）这是最佳的（注意，这相当于 N /（1 / X + 1 / Y ），由于 YN /（X + Y）可能不是整数，你可以计算出几个值（如 X 被围捕和是被舍去，反之亦然），然后取最小值，或者就像你说的，你可以四舍五入两个并给出任何剩余的作业到更快的机器。

This seems to be a math question rather than algorithm question. The job distribution would be YN/(X+Y) pages to X, XN/(X+Y) pages to Y. Total time would be XYN/(X+Y) which is optimal (note that it is equivalent to N/(1/X + 1/Y). Since YN/(X+Y) might not be integer, you can just calculate a few values (if X is rounded up and Y is rounded down, and vice versa) , then take the minimum. Or as you said, you can round down both and give any remaining jobs to the faster machine.

这篇关于算法由两个遗嘱执行人共享工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！