推 JIWP: 大師 12/07 19:16
※ 編輯: Rushia (49.158.191.3 臺灣), 12/07/2024 19:18:02
推 Furina: 大師 12/07 19:17
推 oin1104: 大師 12/07 19:20
https://leetcode.com/problems/minimum-limit-of-balls-in-a-bag
1760. Minimum Limit of Balls in a Bag
給你一個陣列表示袋子，每個袋子裡有一些球，你可以把任意袋子裡的球分成兩堆放到
新的袋子最多 maxOperations 次，求出分完之後MAX(袋子1球數, 袋子2球數, ...)
最小是多少。
思路：
求最大最小，滿明顯要用二分搜索，選定一個搜尋值x，把每個袋子都分成n個不多於x
的更小袋子，如果滿足就繼續縮小x，否則增加小袋子的大小。
Java code:
--------------------------------------------
class Solution {
public int minimumSize(int[] nums, int maxOperations) {
int l = 1;
int r = (int) 1E9;
while (l <= r) {
int mid = l + (r - l)/2;
boolean isOk = check(nums, maxOperations, mid);
if (isOk) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
boolean check(int[] nums, int maxOperations, int x) {
for (int num : nums) {
if (num > x) {
maxOperations -= ((num / x) - 1 + (num % x == 0 ? 0 : 1));
}
if (maxOperations < 0) return false;
}
return true;
}
}
--------------------------------------------
--
https://i.imgur.com/O931L58.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.158.191.3 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1733570198.A.81C.html