7.月度开销

梦想是能睡八小时的猪 / 2023-08-04 / 原文

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