题解 | #分石子#

一.题目描述
NC565分石子
有n堆石子堆，第i堆一共有ai个石子。对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。现在需要通过分裂得到m堆石子，求这m堆石子的最小值最大可以是多少？
图片说明
二.算法(暴力)
可以采用暴力模拟的方法来解决，由于将石子不断进行分裂操作所以最大值一定小于等于初始石子堆的最小值，所以我们可以从开始的最小值不断递减去寻找，是否找到一个值可以使石子堆被分成m堆，然后返回这个值，那么这个值就是最小值的最大值，思路很简单，下面是完整代码：

class Solution {
public:
    int solve(int n, long long m, vector<int>& a) {
        long long int mi=1e18;
        //找到初始的石子堆的石子的最小值
        for(int i=0;i<a.size();i++){
            if(a[i]<mi){
                mi=a[i];
            }
        }
        int ans=0;
        //从开始的最小值递减去找最大值
        for(int i=mi;i>0;i--){
            long long int cnt=0;
            for(int j=0;j<n;j++){
                cnt+=a[j]/i;
            }
            if(cnt>=m){
                //找到最大值 并记录且结束循环
               ans=i;
               break;
            }
        }
        //返回最小值的最大值
        return ans;
    }
};

时间复杂度： $O(n^{2})$ 需进行两重循环
空间复杂度： $O(1)$ 不需要额外开辟空间
优缺点：时间复杂度很高，但是思路简单代码实现简单。
三.算法(二分)
图片说明
首先看到最大值的最小值我们应该会联想到二分，基于算法二我们从最小值递减去寻找，如果值大了那么必然不可以分成m堆，如果值小了必然分成的堆数就大于m了，所以存在一个单调性，基于这个我们可以利用二分查找去找到最小值的最大值，下面是完整代码：

class Solution {
public:
    int solve(int n, long long m, vector<int>& a) {
        long long int mi=1e18;
        //首先同样是找到最小值
        for(int i=0;i<a.size();i++){
            if(a[i]<mi){
                mi=a[i];
            }
        }
        //确定二分查找的左右边界
        int l=1,r=mi+1;
        while(l+1<r){
            int mid=(l+r)>>1;
            long long int cnt=0;
            //判断此时的值是不是可以将石子分成m堆
            for(int i=0;i<n;i++){
                cnt+=a[i]/mid;
            }
            if(cnt<m){
                r=mid;
            } else{
                l=mid;
            }
        }
        return l;
    }
};

时间复杂度： $O(nlogn)$ 二分都可以实现的复杂度
空间复杂度： $O(1)$ 不需要额外空间
优缺点：时间复杂度很低，但是二分实现细节太多，代码虽然简单，但是不好实现