python题目58：工厂流水线调度

题目描述

有n个工厂要加工一批零件，每个工厂需要加工的零件数量是不同的，且每个工厂加工一个零件所需时间也不同。现在需要将这些工厂分配到m条流水线上加工，每条流水线的长度是相同的，且每个工厂只能被分配到一个流水线上。请你编写一个函数，计算出所有工厂加工完这批零件所需的最短时间。

输入描述:

输入文件的第一行包含两个整数n和m，表示工厂数量和流水线数量。第二行包含n个整数，表示每个工厂需要加工的零件数量。第三行包含n个整数，表示每个工厂加工一个零件所需的时间。

输出描述:

输出一个整数，表示所有工厂加工完这批零件所需的最短时间。

样例输入

5 2
5 4 3 2 1
5 4 3 2 1

样例输出

15

解题思路

这是一个二分答案的问题。

我们首先可以发现，这个问题是一个单调性问题，即当流水线数量越多，加工时间一定越短。因此我们可以使用二分答案的方法来解决这个问题。

我们首先可以考虑每一个二分答案，然后对于每个流水线来说，贪心地将工厂分配到流水线上，在分配过程中，对于每个流水线来说，都是从最长的工厂开始分配的。如果分配完之后，所有流水线加工的零件数量都小于总的零件数量，那么说明当前二分答案过大，否则说明当前二分答案过小。通过这样不断的二分，最终就可以得到最小的加工时间。

具体来说，我们首先需要计算出所有工厂加工完所有零件所需的总时间sum。然后将答案的下界设置为sum/m，上界设置为sum。然后我们可以进行二分答案的操作，对于每个二分答案mid，我们需要用贪心的方法将工厂分配到流水线上，这里我们可以使用一个二维数组f[i][j]表示前i个工厂分配到j条流水线上所需的最短时间。具体来说，对于每个工厂i，我们需要枚举当前工厂所在的流水线k，然后计算出分配到其他流水线上的工厂所需的最短时间，然后取其中的最小值即可。时间复杂度为O(nm^2log(sum))。

参考代码

下面是参考代码：