题解 | #分石子#

题目：

有n堆石子堆，第i堆一共有a[i]个石子。可以对任意一堆石子数量大于1的石子堆进行分裂操作，分裂成两堆新的石子数量都大于等于1的石子堆。需要通过分裂得到m堆石子，他想知道这m堆石子的最小值最大可以是多少？

方法一：暴力查找

要查找的最大的最小值在 $[1, m i n (a [i])]$ 之间，因此只需要在这个区间内查找符合条件的值即可，从后往前枚举 $m i n (a [i])$ 到1之间的数字，假设每堆分成 $a [j] / i$ 堆，累加堆数为 $s u m (a [j] / i)$ ，如果 $s u m < m$ ，说明最小堆的值需要减小才可以分出更多的堆数；当堆数大于等于m,说明找到符合条件的值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m long长整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, long m, int[] a) {
        // write code here
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(a[i],min);
        }
        int i;
        for(i=min;i>=1;i--){//从后往前查找
            int sum=0;
            for(int j=0;j<a.length;j++){
                sum+=(a[j]/i);
            }
            if(sum>=m)break;//找到第一个使得分的堆数大于等于m的值即为最大的最小值
        }
        return i;
    }
}

复杂度：

时间复杂度： $O (m i n (a [i]) * n)$ ,外层循环最差循环min(a[i])次，内层循环n次
空间复杂度： $O (1)$ ,额外变量的空间复杂度为常数级

方法二：二分查找

思路：

显然，方法一中在[1,min(a[i])]之间查找最小值时间复杂度过高，可以采用二分查找算法，左指针left置于1,右指针right置于min(a[i])，计算每堆平均分 $a [i] / m i d$ 堆时可以分得的堆数，因为每一大堆分成的每一小堆中的值已经按最小值mid计算，如果分得的堆数仍然小于m，则mid的值位于右区间，因此往右区间查找；否则，当堆数大于等于m时，mid可能为目标值也可能可以再增大一点堆数也不会改变，因此继续往左区间查找，直到left>right；此时返回应该返回使得left>right的mid值，所以返回left-1

alt

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m long长整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, long m, int[] a) {
        // write code here
        int min=Integer.MAX_VALUE;
        for(int i=0;i<n;i++){
            min=Math.min(a[i],min);
        }//最大的最小值在1到min(a[i])间查找
        int left=1,right=min;
        while(left<=right){
            int mid=(left+right)>>1;
            int sum=0;
            for(int i=0;i<n;i++){
                sum+=(a[i]/mid);//当最小值为mid时平均分的堆数
            }
            if(sum<m)right=mid-1;//堆数小于需要分的堆数，最小值往左边查找，增大堆数
            else if(sum>=m){left=mid+1;}//堆数大于等于要分的堆数，最小值可能是mid也可能稍微大一点，因此往右边查找
        }
        return left-1;//要返回mid，因此需要减去1
    }
}

复杂度：

时间复杂度： $O(nlog_{2}(min(a[i])))$ ,二分查找的时间复杂度为 $O(log_{2}(min(a[i])))$
空间复杂度： $O (1)$ ,额外变量的空间复杂度为常数级