rust 解法, 执行用时: 19 ms, 内存消耗: 4.3 MB, 提交时间: 2025-02-12 09:26:19

impl Solution {
    pub fn minimum_size(nums: Vec<i32>, max_operations: i32) -> i32 {
        let check = |m: i32| -> bool {
            let mut cnt = 0;
            for &x in &nums {
                cnt += ((x - 1) / m) as i64;
            }
            cnt <= max_operations as i64
        };

        let mut left = 0; // 循环不变量 check(left) == false
        let mut right = *nums.iter().max().unwrap(); // 循环不变量 check(right) == true
        while left + 1 < right {
            let mid = left + (right - left) / 2;
            if check(mid) {
                right = mid;
            } else {
                left = mid;
            }
        }
        right
    }
}

javascript 解法, 执行用时: 43 ms, 内存消耗: 60.8 MB, 提交时间: 2025-02-12 09:26:03

/**
 * @param {number[]} nums
 * @param {number} maxOperations
 * @return {number}
 */
var minimumSize = function(nums, maxOperations) {
    function check(m) {
        let cnt = 0;
        for (const x of nums) {
            cnt += Math.ceil(x / m) - 1;
        }
        return cnt <= maxOperations;
    }

    let left = 0; // 循环不变量 check(left) == false
    let right = Math.max(...nums); // 循环不变量 check(right) == true
    while (left + 1 < right) {
        const mid = Math.floor((left + right) / 2);
        if (check(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    return right;
};

golang 解法, 执行用时: 36 ms, 内存消耗: 10.5 MB, 提交时间: 2025-02-12 09:25:50

func minimumSize(nums []int, maxOperations int) int {
    left, right := 1, slices.Max(nums)
    return left + sort.Search(right-left, func(m int) bool {
        m += left
        cnt := 0
        for _, x := range nums {
            cnt += (x - 1) / m
        }
        return cnt <= maxOperations
    })
}

java 解法, 执行用时: 26 ms, 内存消耗: 59.1 MB, 提交时间: 2025-02-12 09:25:27

class Solution {
    public int minimumSize(int[] nums, int maxOperations) {
        int mx = 0;
        for (int x : nums) {
            mx = Math.max(mx, x);
        }

        int left = 0; // 循环不变量 check(left) == false
        int right = mx; // 循环不变量 check(right) == true
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (check(nums, maxOperations, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }

    private boolean check(int[] nums, int maxOperations, int m) {
        long cnt = 0;
        for (int x : nums) {
            cnt += (x - 1) / m;
        }
        return cnt <= maxOperations;
    }
}

python3 解法, 执行用时: 497 ms, 内存消耗: 29.3 MB, 提交时间: 2025-02-12 09:25:03

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        def check(m: int) -> bool:
            cnt = 0
            for x in nums:
                cnt += (x - 1) // m
            return cnt <= maxOperations
        return bisect_left(range(max(nums)), True, 1, key=check)

golang 解法, 执行用时: 160 ms, 内存消耗: 9.3 MB, 提交时间: 2022-12-06 13:54:07

func minimumSize(nums []int, maxOperations int) int {
    sort.Ints(nums)
    var operations = func(max int) int {
        var op int
        for _, num := range nums {
            op += (num-1)/max
        }
        return op
    }
    var l, r = 1, nums[len(nums)-1] //1)真二分查找
    for l<=r {
        mid := (l+r)/2
        if operations(mid) <= maxOperations {
            r = mid-1
            continue
        }
        l = mid+1
    }
    return l
}

cpp 解法, 执行用时: 168 ms, 内存消耗: 54.5 MB, 提交时间: 2022-12-06 13:53:44

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int left = 1, right = *max_element(nums.begin(), nums.end());
        int ans = 0;
        while (left <= right) {
            int y = (left + right) / 2;
            long long ops = 0;
            for (int x: nums) {
                ops += (x - 1) / y;
            }
            if (ops <= maxOperations) {
                ans = y;
                right = y - 1;
            }
            else {
                left = y + 1;
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 964 ms, 内存消耗: 24 MB, 提交时间: 2022-12-06 13:53:16

class Solution:
    def minimumSize(self, nums: List[int], maxOperations: int) -> int:
        # 【参考提示】【重点：理解题意，将题目转化为可以实现的问题】如果一个袋子最多只能装x个，
        # 需要拆分y次；每个袋子能能装的球数越多，则需要拆分的次数越少（具有单调性）
        # 当y>maxOperations时，说明x不合题意，则x+=1，第一次当y=maxOperations时的x即为符合题意的答案（此过程可以用二分查找）

        def oper_time(x):
            # x是每个袋子最多装的球个数，返回拆分次数
            oper = 0
            for bag in nums:
                if bag > x:
                    oper += (bag-1)//x
            return oper

        # 进行二分查找 因为oper_time是随着x的增加单调递减的
        l, r = 1, max(nums)
        if oper_time(l) == maxOperations:
            return l
        while l < r:
            mid = (l+r)//2
            if oper_time(mid) <= maxOperations:
                r = mid
            else:
                l = mid + 1
        return l