题解

题目难度：中等难度

知识点：二分法、查找、数组

首先考虑：这是一道查找题，可确定最小值的范围，再使用方法逐渐逼近这个最优解。

二分法逼近最小值

首先明确这个最小值一定是介于（max(nums),sum(nums))之间，因此我们可以使用二分查找来缩小范围。
第一步：先确定个mid=（sum+max）/2的值，以这个值为界限，
第二步：从左向右放入值，直到放入的值总和已经>mid，以此为一个分割划分为一个组，
第三步：再继续放入，一旦又大于mid则再次分割。
第四步：最后如果最后的组数大于要求划分的组数，说明mid值太小，这个最小值要比mid大，最小值处在（mid,sum）之间。否则处在（max,mid）之间。当然，如果组数等于要求的数时，最小值也可能还可以再小。

以示例说明：1 4 2 3 5 ；最大值5，和为15，Mid等于10。M表示所求的值

#include <bits/stdc++.h>
using namespace std;
//创建一个判断函数，a[]保存这个数组，Mid表示这个值，n表示数字个数，m表示最多分为的组数
bool exist(int a[], int mid, int n, int m)
{
    int cnt = 1;
    int sum = 0;
    for (int i = 0;i < n;i++)
    {
        if (sum + a[i] <= mid)
            sum += a[i];
        else
        {
            sum = a[i];
            cnt++;
            if (cnt > m)
            {
                return false;
            }
        }

    }
    return true;
}
int main()
{
    int n, m, num, max = 0, sum = 0;
    cin>>n>>m;
    int a[n];
    for (int i = 0;i < n;i++)
    {
        int x;
        cin>>x;
        a[i]=x;
        if (a[i] > max)
        {
            max = a[i];
        }
        sum += a[i];
    }
    int mid;
    while (sum >= max)
    {
        mid = (max + sum) / 2;
        if (exist(a, mid, n, m))
        {
            sum = mid-1;
        }
        else
        {
            max = mid + 1;
        }
    }
    cout<<max<<endl;
}