题解 | #分石子#

思路：

题目的主要信息：

• 现有n堆石子，每堆数量记录在数组a
• 可以对任意石子数大于1的堆分裂成两堆数量大于等于1的石子
• 现需要分裂成m堆石子()，问这m堆石子最小值最大可以是多少？

方法一：暴力法
具体做法：
我们都知道分裂只会让石子更少，因此最小值一定小于等于分裂前数组最开始的最小值。因此我们从数组分裂前的最小值开始依次往下找，直到为最小值为1.
每次找i是否可行的时候，我们查看是否有大于等于m堆石子，其中每堆数量都是不小于i。某堆数量除以i向下取整就得到原始的每堆可以分成的数量，只需要检查将数量累加查看是否大于等于m即可。

class Solution {
public:
    int solve(int n, long long m, vector<int>& a) {
        int Max = *min_element(a.begin(), a.end()); //a元素最小值
        int i = Max;
        for(; i > 0; i--){  //以a元素最小值为最大，直到1
            long long temp = 0;
            for(int j = 0; j < n; j++)
                temp += a[j] / i; //计算堆数
            if(temp >= m) //达到堆数，跳出循环
                break;
        }
        return i;
    }
};

复杂度分析：

• 时间复杂度：，两层遍历，最坏情况遍历min(a_i)到1，每次检查的时候遍历数组a，*min_element函数复杂度为，较小故舍去
• 空间复杂度：，常数变量空间

方法二：二分法
具体做法：
对于上述暴力的问题，相当于是在一个有序的序列中找到一个合适的数，我们可以用二分法。
上述方法一遍历的终点和起点作为二分的左右起点，首先检查中间值，如果中间值堆数不够，说明最小值还要更小，缩小右边界到中间值；如果中间值堆数已经够了，说明最小值可以更大，缩小左边界到中间只，依次类推直接只剩一个点，和二分查找一致。

class Solution {
public:
    int solve(int n, long long m, vector<int>& a) {
        int left = 1;
        int right = *min_element(a.begin(), a.end()) + 1;
        //从1到数组最小值开始二分找最大化的最小值
        while(left < right - 1){
            int mid = (left + right) / 2;
            long long temp = 0;
            //最小分为中值
            for(int i = 0; i < n; i++){
                temp += a[i] / mid; //计算堆数
            }
            if(temp < m)  //堆数不够，缩小最大值
                right = mid;
            else
                left = mid;
        }
        return left;
    }
};

复杂度分析：

• 时间复杂度：，二分法将外层循环减少到的对数级，，内层循环不变，还是遍历数组a，*min_element函数复杂度为，较小故舍去
• 空间复杂度：，常数空间