这个题目是最小M子段和本尊！也是最大子段和的升级版，由于最大字段和较简单在这里就不写了
link
给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。
注意: 数组长度 n 满足以下条件:
1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)示例:
输入: nums = [7,2,5,10,8] m = 2
输出: 18
解释: 一共有四种方法将nums分割为2个子数组。 其中最好的方式是将其分为[7,2,5] 和 [10,8]， 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
B站视频教程
题解
就是给定一个麻袋的容量k，看把nums的物品装袋子，能装多少袋，如果袋子数量多于m，则增大袋子容量；如果袋子数量小于m，则减小容量；
class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); if(n == 0) return 0; int maxv = 0; int sum = 0; for(int i = 0; i < n; ++i){ maxv = max(maxv, nums[i]); sum += nums[i]; } // 遍历容量，袋子大小从top到down, down设为nums中的最小值，top为总和 int top = sum; int down = maxv; while(down < top){ int mid = (top + down) / 2; // mid 为袋子大小 int count = 1; // count 为分的组数,至少为1组 int tmp = 0; for(int i = 0; i < n; ++i){ if(tmp + nums[i] > mid){ tmp = nums[i]; count++; } else{ tmp += nums[i]; } } if(count > m){ down = mid + 1; } else{ top = mid; } } return down; } };官方题解：
class Solution { public: int splitArray(vector<int>& nums, int m) { int n = nums.size(); vector<vector<long long>> f(n + 1, vector<long long>(m + 1, LLONG_MAX)); vector<long long> sub(n + 1, 0); for (int i = 0; i < n; i++) { sub[i + 1] = sub[i] + nums[i]; } f[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= min(i, m); j++) { for (int k = 0; k < i; k++) { f[i][j] = min(f[i][j], max(f[k][j - 1], sub[i] - sub[k])); } } } return (int)f[n][m]; } };这个题目是 leetcode 410. 分割数组的最大值的升级版，加了一个条件：每个子数组可以任意减去其中一个元素。
link
为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。
在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。
我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。
示例 1：
输入：time = [1,2,3,3], m = 2
输出：3
解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。
示例 2：
输入：time = [999,999,999], m = 4
输出：0
解释：在前三天中，小张每天求助小杨一次，这样他可以在三天内完成所有的题目并不花任何时间。
限制：
1 <= time.length <= 10^51 <= time[i] <= 100001 <= m <= 1000这道题是 leetcode 410. 分割数组的最大值 的升级版，加了一个条件： 题目意思为： 给定一个数组，将其划分成 MM 份，使得每份元素之和最大值最小，每份可以任意减去其中一个元素。 官方题解 很精炼，很清楚。
下面代码，是看了官方题解后自己又敲了一遍，比官方的那个题解速度更快，达到了99%，因为改了下面几行：
int high = *max_element(time.begin(), time.end()); int sum = accumulate(time.begin(), time.end(), 0); if(m == 1) return sum - high; else high = sum - high;不过仍然两个地方不明白：
为啥是 “<=” ?为啥是 “high = mid - 1” ?就是在每次check的地方，要去掉一个最大值，因为每天都有一次场外求助的机会，要使得所用时间最少，那自然应该场外求助那个最难的，也就是time最长的那个。 然后，在贪心判断那里，原来在410题中，是直接判断sum+nums[i] 是否超过了口袋的容量，但是，现在，这里要判断，sum+min(nums[i], maxtime)， 因为如果当前时间nums[i]比maxtime大的话，那应该把当前这个题作为场外求助，把原来的maxtime位置的题目自己做。
可能官方解释的更清楚一些，还是去看一下官方题解吧。
class Solution { public: int minTime(vector<int>& time, int m) { if(time.size() == 0 || m < 1) return 0; // 初始化所用时间的最短与最长 int low = 0; int high = *max_element(time.begin(), time.end()); int sum = accumulate(time.begin(), time.end(), 0); if(m == 1) return sum - high; else high = sum - high; while(low <= high){ // 这里为什么是<=？ int mid = low + (high - low) / 2; if(check(time, mid, m)){ // 如果天数低于等于m 则减少刷题时间 high = mid - 1; } else { low = mid + 1; } } return low; } bool check(vector<int>& time, int mid, int m){ int cnt = 1; int totaltime = 0; int maxtime = time[0]; for(int i = 1; i < time.size(); ++i){ int nexttime = min(time[i], maxtime); if(totaltime + nexttime > mid){ totaltime = 0; cnt++; maxtime = time[i]; } else{ totaltime += nexttime; maxtime = max(maxtime, time[i]); } } return cnt <= m; } };这个题目也是二分+贪心的应用，都算是一个系列的
link
珂珂喜欢吃香蕉。这里有 N 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 K 根。如果这堆香蕉少于 K 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K（K 为整数）。
示例 1：
输入: piles = [3,6,7,11], H = 8 输出: 4
示例 2：
输入: piles = [30,11,23,4,20], H = 5 输出: 30
示例 3：
输入: piles = [30,11,23,4,20], H = 6 输出: 23
提示：
1 <= piles.length <= 10^4piles.length <= H <= 10^91 <= piles[i] <= 10^9寻找最小速度k， 最小速度为1； 最大速度为max_element(piles); 二分查找不断缩小右边界；
代码：
class Solution { public: int minEatingSpeed(vector<int>& piles, int H) { if(piles.size() == 0 || H < 1) return 0; int maxv = 0; for(int pile : piles){ maxv = max(maxv, pile); } int low = 1; int high = maxv; while(low < high){ int mid = low + (high - low)/2; if(canEat(piles, mid, H)){ high = mid; } else{ low = mid + 1; } } return low; } bool canEat(vector<int>& piles, int speed, int H){ int sum = 0; for (int pile : piles) { //向上取整 sum += ceil(pile * 1.0 / speed); } return sum <= H; } };