题目

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

方法一:暴力查找

要查找的最大的最小值在[1,min(a[i])][1,min(a[i])][1,min(a[i])]之间,因此只需要在这个区间内查找符合条件的值即可, 从后往前枚举min(a[i])min(a[i])min(a[i])到1之间的数字,假设每堆分成a[j]/ia[j]/ia[j]/i堆,累加堆数为sum(a[j]/i)sum(a[j]/i)sum(a[j]/i),如果sum<msum<msum<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(min(a[i])n)O(min(a[i]) * n)O(min(a[i])n),外层循环最差循环min(a[i])次,内层循环n次
  • 空间复杂度:O(1)O(1)O(1),额外变量的空间复杂度为常数级

方法二:二分查找

思路:

显然,方法一中在[1,min(a[i])]之间查找最小值时间复杂度过高,可以采用二分查找算法, 左指针left置于1,右指针right置于min(a[i]),计算每堆平均分a[i]/mida[i]/mida[i]/mid堆时可以分得的堆数,因为每一大堆分成的每一小堆中的值已经按最小值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(nlog2(min(a[i])))O(nlog_{2}(min(a[i])))O(nlog2(min(a[i]))),二分查找的时间复杂度为O(log2(min(a[i])))O(log_{2}(min(a[i])))O(log2(min(a[i])))
  • 空间复杂度:O(1)O(1)O(1),额外变量的空间复杂度为常数级