Re: [閒聊] 每日leetcode

看板Marginalman作者Rushia (早瀬ユウカの体操服 )時間1年前 (2024/12/07 19:16)推噓3(3推 0噓 0→)

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