7.月度开销
【题目】
农夫约翰是一个精明的会计师。他意识到自己可能没有足够的钱来维持农场的运转了。他计算出并记录下了接下来 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; }