問(wèn)題描述
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){}
給出一個(gè)數(shù)組來(lái)表示派里面有多少片，然后n個(gè)人，要求每人個(gè)都得到同樣多的片數(shù)，而且每個(gè)人只能從一個(gè)派里面得到多搀。
舉例來(lái)說(shuō)撇眯，假設(shè)片數(shù)是[4,5,7]值桩，然后人數(shù)是2开皿，最大片數(shù)就是4.
詢問(wèn)補(bǔ)充
沒(méi)什么好問(wèn)的锡足。
思路闡述
暴力破解
暴力破解的話忱屑，就是片數(shù)從max(pieSlices)到1都試一遍蹬敲，什么時(shí)候可以了就是最大值。
之所以是最大的為邊界莺戒，原理很明顯伴嗡，如果超過(guò)了，那么一個(gè)派就不可能滿足一個(gè)人从铲。
不能以最小值為邊界瘪校，例如[1,10,10]，2個(gè)人名段，每人可以分到10片阱扬。
那么關(guān)鍵就是驗(yàn)證函數(shù)。其實(shí)也簡(jiǎn)單吉嫩，就是每個(gè)派整除要分的片數(shù)价认，最后加起來(lái)和人數(shù)比較一下。這個(gè)過(guò)程是O(p)自娩，p是派的個(gè)數(shù)用踩。
時(shí)間復(fù)雜度O(pm)。
優(yōu)化
優(yōu)化的話就是改成二分查找忙迁。假設(shè)最大值是m,這個(gè)時(shí)間復(fù)雜度就是O(logm)脐彩。
所以總體時(shí)間復(fù)雜度就是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
總結(jié)
算是一個(gè)比較典型的題目姊扔，難度medium惠奸。
