【题目】
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 N (1 ≤ N ≤ 100,000) 天里每天需要的开销。
约翰打算为连续的M (1 ≤ M ≤ N) 个财政周期创建预算案，他把一个财政周期命名为fajo月。每个fajo月包含一天或连续的多天，每天被恰好包含在一个fajo月里。
约翰的目标是合理安排每个fajo月包含的天数，使得开销最多的fajo月的开销尽可能少。
输入第一行包含两个整数N,M，用单个空格隔开。
接下来N行，每行包含一个1到10000之间的整数，按顺序给出接下来N天里每天的开销。输出一个整数，即最大月度开销的最小值。样例输入
7 5
100
400
300
100
500
101
400
样例输出
500
【思路】
输入样例实际上是计算分组和，不同划分情况，500为最大单月，将其暂时作为上限，尝试划分，那么1月+2月=500没有超，3月+4月=400没有超，5月=500，6月=101，7月=400，分组5个符合要求，最大就是500。
实际上可以转化为一个二分查找的问题，查找可以包含其他月的最小的最大值的分组，且分组数不能超过既定的值。
【代码】
public static int coupons(int n, int m, int[] value) { // min 一天最大开销（单独作为一个月）最好情况 // sum 所有天开销累加（所有天作为一个月）最坏情况 int min = 0; int sum = 0; // 遍历value 计算min和sum for (int i : value) { min = Math.max(min, i); sum += i; } // 二分查找，边界从单月最大开销（min）最好情况 到所有月总和（sum）最坏情况 return binSearch(sum, min, m, n, value); //最大值最小化问题， //思路：贪心+二分（在[min,sum]区间中二分，拿到的值t(假设当前值为最优解即最几个分组的最大值)进行判断： //遍历数组，如果累加值小于t就继续遍历直到大于t,cnt++, } //二分 public static int binSearch(int sum, int min, int m, int n, int[] value) { int l = min; int r = sum; while (l < r) { int mid = (l + r) / 2; //判断如果mid可以满足，那么还能更小，在二分的左边 if (judge(mid, sum, m, n, value)) { r = mid;//mid暂时是最优解，所以要包括在内 } else { //判断如果mid不可以满足，分组数要大于给定值，最优解更大，在二分的右边 l = mid + 1; } } return r; } public static boolean judge(int min, int sum, int m, int n, int[] value) { // count记录分组的数量; int count = 0; // temp保留每次的累加值 int temp = 0; for (int i = 0; i < n; i++) { //分组个数大于等于m必定无最优解 //(等于也算因为cnt已经等于目标分组数，还没分完就超了)，小于m才可能有最优解 if (count >= m) return false; // 如果当前遍历那一天的开销累加之前的比单月的最大开销还小，那么还能包含在一个月内，累加 if (temp + value[i] <= min) { temp += value[i]; } else { //否则 已经超出了单月最大开销，那么将这一天的开销作为新的一个月起始 并增加一个分组 temp = value[i]; count++; } } return true; }