1. 题意

给定一个数组，和一个最多次操作次数。每次操作可以将数组中的一个数$x$分成两个数$tx-t$。问$maxOperationCnt$次操作后，数组中最大的数最小的值是多少。

2. 题解

这个题，我们需要转换思路，不要去想怎么分，而是经过操作后数组中有几个数。对于一个数$x$，要使它分割后小于$y$, 我们肯定分割后尽量都分成每个数都为$y$, 因此最后的堆数为$\lceil \frac{x}{y}\rceil$, 分割的次数为$\lfloor \frac{x-1}{y}\rfloor$。

再将数组排好序数，进行二分，每次尝试数$x$，看需要的分割数$splitCnt$是否小于等于$maxOperationCnt$
s p l i t C n t = ∑ x i ∈ S ⌊ x i − 1 y ⌋ S : = { x i , x i > y } splitCnt=\sum_{x_i\in S}\lfloor\frac{x_i-1}{y}\rfloor\quad \\S :=\{x_i,x_i >y\} splitCnt=xi​∈S∑​⌊yxi​−1​⌋S:={xi​,xi​>y}

• 代码一

class Solution {
public:

    int logcnt(int base,int v) {
        int ans = 0;
        while (base < v) {
            v = (v + 1)/2;
            ans++;
        }
        return ans;
    }
    bool check(const vector<int> &nums, int val,int bid, int maxCnt) {
        int sz = nums.size();
        int ndcnt = 0;
        for (int i = bid;i < sz;i++) {
            ndcnt += (nums[i]  - 1) / val;
        }

        return ndcnt <= maxCnt;
    }
    int FindNotLess(const vector<int> &a, int v) {
        int l = 0;
        int r = a.size();

        while (l < r) {
            int mid = (l + r) >> 1;
            if (a[mid] <= v)
                l = mid + 1;
            else 
                r = mid - 1;
        }

        return l;
    }
    int minimumSize(vector<int>& nums, int maxOperations) {

        sort(nums.begin(), nums.end());
        
        int sz = nums.size();
        int l =  1;
        int r = *nums.rbegin();
        
        while (l < r) {
            int val = (l + r) >> 1;

            // int idx = FindNotLess(nums, val);
            vector<int>::iterator it = upper_bound(nums.begin(), nums.end(), val);
            int ndCnt = 0;
            // for (int i = idx;i < sz;i++) {
            //     ndCnt += (nums[i] - 1) / val;
            // }
            for (;it != nums.end(); it++) {
                ndCnt += ((*it) - 1)/val;
            }
            if (ndCnt <= maxOperations) {
                r = val;
            }
            else {
                l = val + 1;
            }
        }

        return l;
    }
};

其实不需要排序的，直接尝试遍历整个数组就好了

• 03xf的代码

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        auto check = [&](int m) -> bool {
            long long cnt = 0;
            for (int x : nums) {
                cnt += (x - 1) / m;
            }
            return cnt <= maxOperations;
        };

        int left = 0; // 循环不变量 check(left) == false
        int right = ranges::max(nums); // 循环不变量 check(right) == true
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? right : left) = mid;
        }
        return right;
    }
};

参考

03xf