问题描述
Given a list of pies and the number of slices in each pie, calculate the maximum number of slices that n people could receive if each person got the same amount of slices and did not get slices from more than 1 pie.
The function looks like this:
public int getMaxSlices(List<Integer> pieSlices, int n){}
给出一个数组来表示派里面有多少片，然后n个人，要求每人个都得到同样多的片数，而且每个人只能从一个派里面得到。
举例来说，假设片数是[4,5,7]，然后人数是2，最大片数就是4.
询问补充
没什么好问的。
思路阐述
暴力破解
暴力破解的话，就是片数从max(pieSlices)到1都试一遍，什么时候可以了就是最大值。
之所以是最大的为边界，原理很明显，如果超过了，那么一个派就不可能满足一个人。
不能以最小值为边界，例如[1,10,10]，2个人，每人可以分到10片。
那么关键就是验证函数。其实也简单，就是每个派整除要分的片数，最后加起来和人数比较一下。这个过程是O(p)，p是派的个数。
时间复杂度O(pm)。
优化
优化的话就是改成二分查找。假设最大值是m,这个时间复杂度就是O(logm)。
所以总体时间复杂度就是O(plogm)。
代码
class Solution:
def getMaxPiece(self, L, n):
low, high = 0, sum(L)//n
while low <= high:
mid = (low + high) // 2
if sum(x//mid for x in L) >= n:
low = mid + 1
else:
high = mid - 1
return low - 1
总结
算是一个比较典型的题目，难度medium。
