NC569 题解 | #分组#

题意分析

• 给你一个长度为n的序列，需要我们将这个序列分为连续的k部分，要求分的所有的情况里面，对于每个部分的数字的和，要求所有的部分数字的和的最小的最大化。
• 样例解释
  有3种分法
  [1],[2,1,5]，数字和分别为1，8，最小值为1
  [1,2][1,5]，数字和分别为3，6，最小值为3
  [1,2,1],[5]数字和分别为4，5，最小值为4
  则最小值的最大值为4。

思路分析

• 我们知道，对于这种类型的题目，要我们求最小值最大化或者最大值最小化的情况，我们一般是可以使用二分的方法进行求解的。我们先利用二分枚举最后的结果。然后对于我们枚举的每个值，我们通过一个函数进行判断。那么这个函数如何判断呢？
• 我们发现，对于最后的结果，我们按照顺序进行划分，如果当前的值超过了我们枚举的mid，那么我们就可以将这些数字划分为同一部分，然后，我们判断最后的划分情况大于等于mid的有多少个，与k进行比较。如果比k大，那么说明我们的枚举的最小值还可以更大。否则，就更小。更新左右区间即可。

• judge函数如下

    // 我们假设最小值为mid
    bool judge(int k,int mid,vector<int>&a){
        int num=0;
        int sum=0;
        for(auto x:a){
            sum+=x;
            if(sum>=mid){
                num++;
                sum=0;
            }
        }
        return num>=k;
    }

写法一 C++版

• 代码如下
  • 假设a数组的和为s，二分的时间复杂度为,judge函数的判断的时间复杂度为.所以总的时间复杂度为
  • 只开了少数几个变量进行求解，空间复杂度为

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    // 我们假设最小值为mid，那么小于最小值的就必须要添一个知道满足大于等于这个mid
    bool judge(int k,int mid,vector<int>&a){
        int num=0;
        int sum=0;
        for(auto x:a){
            sum+=x;
            // 如果这一部分的所有的数字的和大于等于mid，那么就把这些划分为一块
            if(sum>=mid){
                num++;
                sum=0;
            }
        }
        // 最后的块数和k进行比较
        return num>=k;
    }
    int solve(int n, int k, vector<int>& a) {
        // write code here
        int l=0,r=0,mid;
        for(auto x:a){
            r+=x;
        }
        int ans=0;
        while(l<=r){
            mid=(l+r)>>1;
           // std::cout<<"mid:"<<mid<<endl;
            // 如果最后的结果大于等于mid，左边界右移
            if(judge(k,mid,a)){
                l=mid+1;
                ans=max(ans,mid);
            }else{
                // 如果最后的结果小于mid，右边界左移
                r=mid-1;
            }
        }
        return ans;
    }
};

写法二 Go语言版

• 看写Go的不多，那么我来贡献一波go的代码。时间和空间都是100%，QAQ。

• 代码如下

  • 假设a数组的和为，二分的时间复杂度为,judge函数的判断的时间复杂度为.所以总的时间复杂度为
  • 只开了少数几个变量进行求解，空间复杂度为

package main


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param k int整型 
 * @param a int整型一维数组 
 * @return int整型
*/
func solve( n int ,  k int ,  a []int ) int {
    // write code here
    l := 0
    r := 0
    // 先进行遍历得到所有的数字的和作为右边界
    for _, value := range a {
        r+=value
    }
    var mid int
    ans := 0
    for l<=r {
        // 二分区间中点
        mid = (l+r)/2
        num := 0
        sum := 0
        for _, value := range a {
            sum+=value
            if(sum>=mid){
                num++
                sum=0
            }
        }
        // 如果可以分的块数超过k，那么左边界右边移动
        if(num>=k){
            // 维护答案的最大值
            if(ans<mid) {
                ans=mid
            }
            l=mid+1
        }else{
            // 否则右边界左边移动
            r=mid-1
        }
    }

    return ans
}