题目描述

小明的蛋糕工厂每天可以生产的蛋糕数量是由工厂中的机器和工人的数量决定的，即 ( m \times w )。现在他收到了一个大订单，需要尽快生产出 ( n ) 个蛋糕。为了提升生产速度，小明可以使用每天生产的蛋糕去购买额外的机器或工人，每台机器或每个工人的成本是 ( p ) 个蛋糕。

例如，如果工厂起始时有 1 台机器和 2 个工人，每次扩大产能的成本是 1 个蛋糕，为了生产 60 个蛋糕，小明可以这样操作：

第一天：生产 2 个蛋糕，买入 2 台机器（总机器数变为 3）。
第二天：生产 6 个蛋糕，买入 3 台机器，3 个工人（机器数 6，工人数 5）。
第三天：生产 30 个蛋糕。
第四天：再生产 30 个蛋糕，完成订单。
你的任务是帮助小明计算最快多少天能完成订单。

测试样例
样例1：

输入：m = 3, w = 1, p = 2, n = 12
输出：3

样例2：

输入：m = 10, w = 5, p = 30, n = 500
输出：8

样例3：

输入：m = 3, w = 5, p = 30, n = 320
输出：14

样例

blablabla

提供两种二分的方法

算法1

(二分)

blablabla

时间复杂度

参考文献

java代码

 public class Main {
    public static int solution(int m, int w, int p, int n) {
        // 定义check函数




        // 左开右开
        int l = 0, r = n / (m * w) + 2;
        while (l + 1 < r) {
            int mid = (l + r) >> 1;
            if (check(mid,m,w,p,n))
                r = mid;
            else
                l = mid;
        }
        return r;
    }
       public static boolean check(int k,int m, int w, int p, int n) {
                int cake = m * w;
                // 不扩大生产规模就能完成 返回true
                if (cake * k >= n)
                    return true;
                int cnt = 1;
                while (cake < n) {
                    // 可以增加生产资料的数量
                    int add = cake / p;
                    // 均分
                    if (m < w) {
                        int temp = m;
                        m = w;
                        w = temp;
                    }
                    int diff = m - w;
                    if (add <= diff)
                        w += add;
                    else {
                        int total = add + m + w;
                        w = total / 2;
                        m = total - w;
                    }
                    // 蛋糕没用完
                    cake %= p;
                    // 不再扩大生产规模 如果可以在后续时间内完成生产 返回true
                    if (cake + (m * w * (k - cnt)) >= n)
                        return true;
                    // 又过了一天...
                    cnt++;
                    cake += m * w;
                }
                return cnt <= k;
            }


    public static void main(String[] args) {
        // 你可以添加更多测试用例
        System.out.println(solution(3, 1, 2, 12)); // 输出: 3
        System.out.println(solution(10, 5, 30, 500)); // 输出: 8
        System.out.println(solution(3, 5, 30, 320)); // 输出: 14
        System.out.println(solution(3, 1, 2, 12) == 3); // 输出: true
        System.out.println(solution(10, 5, 30, 500) == 8); // 输出: true
        System.out.println(solution(3, 5, 30, 320) == 14); // 输出: true
    }
}

算法2

(二分)

blablabla

时间复杂度

参考文献

java代码

 public class Main {
    public static int solution(int m, int w, int p, int n) {
        int l = 1, r = n / (w * m) + 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (check(mid, m, w, p, n)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
         System.out.println( l );
        return l;
    }

    static boolean check(int days, int m, int w, int p, int n) {
        int cakes = 0;
        //long machines = m;
      //  long workers = w;

        for (int day = 1; day <= days; day++) {
            // 计算当天生产的蛋糕数量
            cakes += m*w;

            // 如果已经生产足够多的蛋糕，返回 true
            if (cakes >= n) {
                return true;
            }

           // 如果蛋糕数量足够购买机器或工人
            while (cakes >= p) {
                // 尽量平衡机器和工人的数量
                if (m < w) {
                    m++;
                } else {
                    w++;
                }
                cakes -= p;
            } 

                    // 不再扩大生产规模 如果可以在后续时间内完成生产 返回true
                    if (cakes + (m * w * (days - day)) >= n)
                        return true;
        }

        // 如果天数内没有生产足够多的蛋糕，返回 false
        return cakes >= n;
    }

    public static void main(String[] args) {
        // 你可以添加更多测试用例
        System.out.println(solution(3, 1, 2, 12) == 3);
        System.out.println(solution(10, 5, 30, 500) == 8);
        System.out.println(solution(3, 5, 30, 320) == 14);
    }
}