详细一点点的二分解法（Java）

解题思路:典型的二分模板题，二分算法可以查找满足同一性质的区间，比如二分查找用来在已排序数列中查找数字5，查找的位置的左边都是小于5，右边都是大于5
，这个题也是一样，用一个函数来代表共同性质，最最小的最大值的左边的值若为子段和最大值分成的段数将大于M，右边的值为子段和最大值可能可以分成M段也可能小于M段，但是分成M段不是最最小的子段和最大值。所以这个题我们查找恰好不能分成M段的子段和最大值，将其+1,就是最小的最大子段和。
注意事项：
参考代码:

import java.util.Scanner;

public class Main {

    static int N,M;

    static int[] sz;

public static void main(String[] args) {

// TODO Auto-generated method stub

        Scanner sc1=new Scanner(System.in);

N=sc1.nextInt();

M=sc1.nextInt();

sz=new int[N];

int H=0;

int left=1;

for(int i=0;i<N;i++)

{

sz[i]=sc1.nextInt();

H+=sz[i];

if(left<sz[i])

{

left=sz[i];

}

}

        int rigth=H,mid=(left+rigth)/2;

while(left<=rigth)

        {

        if(Main.check(mid)==false)

        {

        left=mid+1;

        }

        else

        {

        rigth=mid-1;

        }

        mid=(left+rigth)/2;

        }

System.out.print(mid+1);

}

    static boolean check(int n)//代表区间共同性质

    {

    int H=0;

    int ans=0;

    for(int i=0;i<N;i++)

    {

    if(H+sz[i]>n)

    {

    ans++;

    H=sz[i];

    }

    else

    {

    H+=sz[i];

    }

    }

    if(ans<M)

    {

    return true;

    }

    else

    {

    return false;

    }

    }

}