NC565 题解 | #分石子#

题意分析

• 给出n堆石头以及每堆石头的数量，然后我们可以将任意堆石头数量大于1的分为两堆，问最后分为m堆中，分得的所有堆里面的最小值最大是多少？

思路分析

• 对于这种最小值最大，最大值最小等的问题，一半都是采用的是二分的方法进行处理。我们先判断怎样二分具有单调性。我们二分数组里面的最小值，假设当前的最小值为mid，然后对于这个mid，我们看可以分为多少块，如果我们可以分成k块，k>=m，那么说明我们的最小值可以更大，左边界向右边移动，否则，就将右边界向左边移动。继续二分新的边界。如此下去。

• 对于每个二分的值，我们如何进行处理呢？我们遍历整个数组，然后利用除法看可以将这个分为多少块，最后根据块数移动左右边界即可。

• 我们发现将一堆石头分为两堆，分得的堆数的石头的块数一定是更小的。所以我们可以把区间的初始的最小值作为区间的右端点进行处理。

• 样例解释

• 这里我用了两种写法进行求解
  • 二分区间的范围是[0,1e9]，所以二分的时间复杂度为$O(logMax(a_i))O(logMax(a\_i))$,judge函数需要遍历整个数组，时间复杂度为$O(n)O(n)$,所以总的时间复杂度为$O(nlogMax(a_i))O(nlogMax(a\_i))$
  • 过程中只用了少数几个变量进行求解，空间复杂度为$O(1)O(1)$

写法一 C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m long长整型 
     * @param a int整型vector 
     * @return int整型
     */
    typedef long long ll;
    bool judge(ll x,int n,ll m,vector<int> &a){
        ll sum=0;
        // 遍历数组计算这种分法的堆数
        for(auto y:a){
            sum+=y/x;
        }
        // 如果分成的堆数超过了m，返回true,那么说明这种分法不行，最小值应该更大
        return sum>=m;
    }
    int solve(int n, long long m, vector<int>& a) {
        // write code here
        ll l=1,r=a[0],mid;
        for(auto x:a){
            r=min(r,(ll)x);
        }
        // 二分当前的最小值
        while(l<r){
            mid=(l+r+1)>>1;
           // 如果按照这种最小值进行划分得到的块数超过了m,那么说明最小值可以更大，左边界右移
            if(judge(mid,n,m,a)){
                l=mid;
            }else{
                r=mid-1;
            }
        }
        
        return l;
    }
};

写法二 GO

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m long长整型 
 * @param a int整型一维数组 
 * @return int整型
*/
// judge函数判断二分的这个最小值是否满足可以将石头分为超过m组
func judge(n int, x int, m int64, a []int) bool {
    var sum int64
    sum  = 0
    for i := 0; i < n; i++{
        sum += int64(a[i]/x)
    }
    
    return sum >= m
}
func solve( n int ,  m int64 ,  a []int ) int {
    // write code here
    l := 1
    r := a[0]
    // 最后的答案一定不会大于原来的切片的最小值
    for i := 1; i < n; i++ {
        if r > a[i] {
            r = a[i]
        }
    }
    
    for {
        if l>=r {
            break
        }
        mid := (l+r+1)>>1
        // 如果这个值可以分为超过m组，那么说明这个最小值可以更大
        if(judge(n,mid,m,a)){
            l=mid
        }else{
            r=mid-1
        }
    }
    
    return l
}