所有人喝完咖啡并洗完咖啡杯，至少来到时间点

问题描述：

        数组arr代表每一个咖啡机冲一杯咖啡的时间，每个咖啡机只能串行的制造咖啡。现在有n个人需要喝咖啡，只能用咖啡机来制造咖啡。认为每个人喝咖啡的时间非常短，冲好的时间即是喝完的时间。每个人喝完之后咖啡杯可以选择洗或者自然挥发干净，只有一台洗咖啡杯的机器，只能串行的洗咖啡杯。洗杯子的机器洗完一个杯子时间为a，任何一个杯子自然挥发干净的时间为b。
        四个参数：arr, n, a, b
        假设时间点从0开始，返回所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点。

思路一：暴力尝试法

代码：

    /**
     *
     * @param arr 每一个咖啡机冲一杯咖啡的时间
     * @param n n个人需要喝咖啡
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @return 所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点
     */
    public static int minTime1(int[] arr,int n ,int a,int b){
        //用于记录每台咖啡机目前来到的时间点
        int[] times = new int[arr.length];
        //记录每个人拿到咖啡时的时间
        int[] drink = new int[n];
        return forceMake(arr,times,0,drink,n,a,b);
    }
 
    /**
     *
     * @param arr 每一个咖啡机冲一杯咖啡的时间
     * @param times 用于记录每台咖啡机目前来到的时间点
     * @param kth 记录目前是第几号咖啡机
     * @param drink 记录每个人拿到咖啡时的时间
     * @param n n个人需要喝咖啡
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @return 主要是冲咖啡流程，返回给洗咖啡杯流程每杯咖啡冲好的时间  所有人喝完咖啡并洗完咖啡杯的全部过程结束后，至少来到什么时间点
     *
     *              (每个人暴力尝试用每一个咖啡机给自己做咖啡）
     */
    public static int forceMake(int[] arr,int[] times,int kth,int[] drink,int n,int a,int b){
        if (kth == n){// kth 从0开始遍历，到n结束，所有的信息都收集完成，即冲咖啡结束，开始洗咖啡杯
            int[] drinkSorted = Arrays.copyOf(drink,kth);
            Arrays.sort(drinkSorted);
            return forceWash(drinkSorted,a,b,0,0,0);
        }
        //当前咖啡机未遍历到第n个人
        int time = Integer.MAX_VALUE;
        for (int i = 0;i//遍历每一台咖啡机
            int work = arr[i];//咖啡机冲一杯咖啡时间
            int pre = times[i];//咖啡机此时到达可以冲咖啡的时间
 
            //若选择这台咖啡机给第 kth 个人冲咖啡，设置好第 kth 个人拿到咖啡的时间和当前咖啡机到达的工作时间点。
            drink[kth] = pre + work;
            times[i] = pre+work;
            //查看后续过程全部完成至少来到的时间点
            time = Math.min(time,forceMake(arr,times,kth+1,drink,n,a,b));
 
            //回溯过程
            drink[kth] = 0;
            times[i] = pre;
        }
        return time;
    }
 
    /**
     *
     * @param drinks 每个人拿到咖啡时的时间点
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @param index 目前到了第index个人冲洗咖啡杯
     * @param washLine  洗杯子的机器目前来的时间点
     * @param time 全部完成工作至少的时间点
     * @return 全部完成至少来到的时间点
     */
    public static int forceWash(int[] drinks,int a,int b,int index,int washLine,int time){
        //全部人的咖啡杯都洗完
        if (index == drinks.length){
            return time;
        }
 
        //咖啡杯没有洗完
        //选择一：当前index号咖啡杯选择用洗咖啡杯机器清洗
        int wash = Math.max(drinks[index],washLine)+a;//冲好咖啡时间和洗咖啡杯机器能工作时间取最大值
        int ans1 = forceWash(drinks,a,b,index+1,wash,Math.max(wash,time));//完成后序过程，取得至少得时间
 
        //选择二：当前index号咖啡杯选择用自然挥发
        int dry = drinks[index]+b;
        int ans2 = forceWash(drinks,a,b,index+1,washLine,Math.max(dry,time));
 
        //选取两种情况中时间点早的返回
        return Math.min(ans1,ans2);
    }

思路二：在思路一得基础上，使用小根堆来优化冲咖啡的过程。

代码：

    /**
     * 小根堆的节点，用于表示每一台咖啡机
     * timePoint 咖啡机当前可以工作的时间点
     * workTime 咖啡机每次冲一杯咖啡的时间
     */
    public static class Machine{
        public int timePoint;
        public int workTime;
 
        public Machine(int t,int w){
            timePoint = t;
            workTime = w;
        }
    }
 
    /**
     * 比较器】
     * 小根堆
     * 当咖啡机当前工作时间和冲一杯咖啡时间和最小时，优先使用
     */
    public static class MachineComparator implements Comparator{
 
        @Override
        public int compare(Machine o1, Machine o2) {
            return (o1.timePoint+o1.workTime)-(o2.workTime+o2.timePoint);
        }
    }
 
    /**
     *    每个人暴力尝试用每一个咖啡机给自己做咖啡，优化成贪心
     * @param arr 每一个咖啡机冲一杯咖啡的时间
     * @param n n个人需要喝咖啡
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @return  全部完成至少来到的时间点
     */
    public static int minTime2(int[] arr,int n, int a, int b){
        PriorityQueue heap = new PriorityQueue<>(new MachineComparator());
 
        for (int i =0;i
            heap.add(new Machine(0,arr[i]));
        }
 
        int[] drinks = new int[n];
        for (int i =0;i
            //小根堆堆顶始终是使用当前咖啡机时最优的答案
            Machine cur = heap.poll();
            cur.timePoint += cur.workTime;
            drinks[i] = cur.timePoint;
            heap.add(cur);
        }
 
        //洗杯子阶段
        return process(drinks,a,b,0,0);
    }
 
    /**
     *
     * @param drinks 记录每个人拿到咖啡时的时间
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @param index 目前是index个人
     * @param washLine drinks[index....],洗杯子的机器什么时候可以接受新的杯子
     * @return 全部完成至少来到的时间点
     */
    public static int process(int[] drinks,int a,int b,int index,int washLine){
        //只剩一个杯子的时候
        if (index==drinks.length-1){
            return Math.min(Math.max(washLine,drinks[index])+a,drinks[index]+b);
        }
 
        //不止一个杯子
        //wash是我当前的咖啡杯，洗完的时间
        //选择洗
        int wash = Math.max(washLine,drinks[index])+a;// 洗完我这一杯，时间来到哪
        int next1 = process(drinks,a,b,index+1,wash);
        int p1 = Math.max(wash,next1);
 
        //选择挥发
        int dry = drinks[index]+b;// 挥发完我这一杯，时间来到哪
        int next2 = process(drinks,a,b,index+1,washLine);
        int p2 = Math.max(dry,next2);
 
        return Math.min(p1,p2);
    }

思路三：思路二的基础上使用动态规划。

代码：

    /**
     *  把方法二洗咖啡杯的暴力尝试进一步优化成动态规划
     * @param arr 每一个咖啡机冲一杯咖啡的时间
     * @param n n个人需要喝咖啡
     * @param a 洗完一个杯子时间为a
     * @param b 任何一个杯子自然挥发干净的时间为b
     * @return  全部完成至少来到的时间点
     */
    public static int minTime3(int[] arr,int n,int a,int b){
        PriorityQueue heap = new PriorityQueue<>(new MachineComparator());
 
        for (int i =0;i
            heap.add(new Machine(0,arr[i]));
        }
 
        int[] drinks = new int[n];
 
        for (int i =0;i
            Machine cur = heap.poll();
            cur.timePoint += cur.workTime;
            drinks[i] = cur.timePoint;
            heap.add(cur);
        }
 
        //当洗杯子时间大于挥发时间时，所有的杯子全部采用挥发方式
        if (a>=b){
            return drinks[n-1]+b;
        }
 
        //二维数组dp 行表示每一个杯子  列表示每一个时间点（最大的时间点为最后一杯咖啡冲好后，用机器清洗杯子）、
        //dp[i][j] 表示从第i个杯子到最后一个杯子，开始时间点为j，最早结束的时间
        int[][] dp = new int[n][drinks[n-1]+n*a];
 
        //二维数组的最后一行表示只剩下最后一个杯子需要清洗时的情况
        for (int i =0;i0].length;i++){
            dp[n-1][i] = Math.min(
                    Math.max(i,drinks[n-1])+a,
                    drinks[n-1]+b
            );
        }
 
        //二维数组的普遍位置
        for (int row = n-2;row>=0;row--){
            int washLine = drinks[row] + (row+1)*a;
            for (int col =0;col
                int wash = Math.max(col,drinks[row])+a;
                dp[row][col] = Math.min(
                        Math.max(wash,dp[row+1][wash]),
                        Math.max(drinks[row]+b,dp[row+1][col])
                );
            }
        }
        return dp[0][0];
    }

测试代码

    public static int[] randomArray(int len,int max){
        int[] arr  = new int[len];
        for (int i =0;i
            arr[i] = (int)(Math.random()*max)+1;
        }
        return arr;
    }
 
    public static void printArray(int[] arr){
        System.out.print("arr : ");
        for (int j =0;j
            System.out.print(arr[j]+" , ");
        }
        System.out.println();
    }
 
    public static void main(String[] args) {
        int len = 5;
        int max = 9;
        int testTime = 50000;
        System.out.println("test begin!");
        for (int i =0;i
            int[] arr = randomArray(len,max);
            int n = (int)(Math.random()*5)+1;
            int a = (int)(Math.random()*5)+1;
            int b = (int)(Math.random()*10)+1;
            int ans1 = minTime1(arr,n,a,b);
            int ans2 = minTime2(arr,n,a,b);
            int ans3 = minTime3(arr,n,a,b);
            if (ans1!=ans2 || ans3!=ans1){
                System.out.println("Oops!");
                printArray(arr);
                System.out.println("ans1 : " + ans1);
                System.out.println("ans2 : " + ans2);
                System.out.println("ans3 : " + ans3);
            }
        }
        System.out.println("test end!");
    }