按顺序给出n个数，将n个数分为m段，使每段的和最大值最小，求该值最小为多少。

按顺序给出 n 个数，将 n 个数分为 m 段，使每段的和最大值最小，求该值最小为多少。

思考当前问题的对立问题： 对于一个值 max_value，判断是否可以将序列切分成连续的 m 段，并且使得每个子段和不大于 max_value 。

定义变量 s，作为当前扩展子段的起始点，初始 s = 0。从 s 出发不断向右扫描，直到 t 位置，满足 sum( a[s…t] ) > max_value， 则将 s[ s, t-1 ] 作为一个子段。令 s = t ，回到步骤（2），直到扫描整个序列。

实现如下：

bool CHECK(int a[], int n, int m, int max_value) { int cnt = 0, sum = 0; for (int i = 0; i < n; ++i){ if (a[i] > max_value) // 若有单个元素值大于 max_vlaue，则无法划分 return false; sum += a[i]; if (sum > max_value){ cnt ++; sum = a[i]; } } cnt++; // 处理最后一个未判断的子段 return cnt <= m; }

原问题要求的是最小的 max_value, 满足一个 max_value 后，则 max_vlaue + 1 也能满足。 故本题中 CHECK 函数也是一个阶跃函数，使用二分逼近能获得最小的max_vlaue。

int BINARY_SEARCH(int a[], int n, int m) { int low = 0, high = inf; // inf µÄÖµ´óÓÚÐòÁÐÖÐËùÓÐÔªËØµÄºÍ while (high > low) { int mid = (low + high) >> 1; if (CHECK(a, n, m, mid)) high = mid; else low = mid + 1; } return high; }