题解 | #分组#

一.题目描述
NV569分组
有一个n个数字的序列a1,a2,a3......an，现在牛牛想把这个序列分成k段连续段，求分出来的k个连续段的段内数字和的最小值最大可以是多少？

二.算法(二分)

题目的意思很容易就可以理解，看到段内数字和的最小值最大可以是多少我们就可以很敏感的知道这是二分问题，下面我们就分析如何去进行二分。首先我们求出数组所以数的和，最小值的最大值一定小于等于，接下来我们对所有数的和进行二分并判断是否对于中值mid能否满足将数组分为k段且每段都大于等于，找到最大值并返回。下面是完整代码：

class Solution {
public:
    //二分情况的判断
    bool ck(int k,vector<int> a,int ans){
        int cnt=0,sum=0;
        for(int i=0;i<a.size();i++){
            sum+=a[i];
            if(sum>=ans){
                sum=0;
                cnt++;
            }
        }
        //可以分成k段且每一段大于等于ans
        if(cnt>=k){
            return true;
        } else {
            return false;
        }
    }
    int solve(int n, int k, vector<int>& a) {
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=a[i];
        }
        int l=0,r=sum;
        //最大值一定是小于等于sum的 进行二分查找
        while(l<r){
            int mid=(l+r+1)>>1;
            if(ck(k,a,mid)){
                l=mid;
            } else {
                r=mid-1;
            }
        }
        return l;
    }
};

时间复杂度： 二分查找的效率比较高
空间复杂度： 不需要额外空间进行存储
优缺点：代码时间效率高，但是二分实现细节难把握
三.算法(java实现)
仔细想一想也没有什么比二分更优的算法了，下面用java实现一下，思路和算法二是一样的，下面是完整代码：

import java.util.*;


public class Solution {
    public static boolean ck(int k,int[] a,int ans){
        int cnt=0,sum=0;
        for(int i=0;i<a.length;i++){
            sum+=a[i];
            if(sum>=ans){
                sum=0;
                cnt++;
            }
        }
        //可以分成k段且每一段大于等于ans
        if(cnt>=k){
            return true;
        } else {
            return false;
        }
    }
    public static int solve(int n, int k, int[] a) {
        int sum=0;
        for(int i=0;i<n;i++){
            sum+=a[i];
        }
        int l=0,r=sum;
        //最大值一定是小于等于sum的 进行二分查找
        while(l<r){
            int mid=(l+r+1)>>1;
            if(ck(k,a,mid)){
                l=mid;
            } else {
                r=mid-1;
            }
        }
        return l;
    }
}

时间复杂度： 二分查找的效率比较高
空间复杂度： 不需要额外空间进行存储
优缺点：代码时间效率高，但是二分实现细节难把握