前往
大廳
主題

LeetCode - 2226. Maximum Candies Allocated to K Children 解題心得

Not In My Back Yard | 2022-12-13 12:00:10 | 巴幣 0 | 人氣 201

題目連結:


題目意譯:
你被給定一個索引值從 0 開始的陣列 candies。陣列中每個元素代表著大小為 candies[i] 的糖果堆。你可以將每一堆分成任意大小以及數量的糖果堆,但是你不得將兩堆糖果堆合併在一起。

你同時也被給定一整數 k。你應將這些糖果堆分配給 k 個小孩並使得每位小孩都拿到相同數量的糖果。每為小孩可以拿走最多一整堆的糖果走,而有些糖果堆可能不會被拿走。

回傳每位小孩所能得到的最大糖果量。

限制:
1 ≦ candies.length ≦ 10 ^ 5
1 ≦ candies[i] ≦ 10 ^ 7
1 ≦ k ≦ 10 ^ 12



範例測資:
範例 1:
輸入: candies = [5,8,6], k = 3
輸出: 5
解釋: 我們可以將 candies[1] 分成大小為 5 以及大小為 3 的糖果堆,且將 candies[2] 分成大小為 5 以及大小為 1 的糖果堆。現在我們有著五堆糖果,且各自大小為 5 、 5 、 3 、 5 和 1。我們可以 3 堆大小為 5 的糖果堆給這 3 個小孩。可以證明每位小孩無法得到多於 5 個糖果。

範例 2:
輸入: candies = [2,5], k = 11
輸出: 0
解釋: 現在有 11 位小孩,但是糖果總共只有 7 個,所以不可能可以確保每位小孩得到至少一個糖果。因此每位小孩都沒有糖果,因此答案為 0。


解題思維:
又是一個可以採取對答案進行二分搜尋法(Binary Search)的題目,如同這題

那要怎麼檢查我們猜的糖果數 m 可不可行呢?

很簡單,我們掃過一次陣列 candies。而根據題目敘述,我們只能分堆不能合併,因此 candies[i] 最多只能分給「candies[i] ÷ m 取整數部分」位小孩。

將每一堆貢獻的小孩數量加總看有沒有超過 k。如果有則代表我們有機會可以試著猜得比 m 還要大;反之,我們需要猜得比 m 還要小。

重複以上猜的步驟最後便可以得到一個可行的最大糖果數,此即為所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作