问题描述：

        数组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

    /*** 小根堆的节点，用于表示每一台咖啡机* 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{@Overridepublic 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

    /***  把方法二洗咖啡杯的暴力尝试进一步优化成动态规划* @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=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;i=0;row--){int washLine = drinks[row] + (row+1)*a;for (int col =0;col

    public static int[] randomArray(int len,int max){int[] arr  = new int[len];for (int i =0;i