题目描述

首先，给你几个数据：
数组arr：表示几个咖啡机，这几个咖啡机生产一杯咖啡所需要的时间就是数组中的值，例如arr=[2,3,7]就表示第一台咖啡机生产一杯咖啡需要2单位时间，第二台需要3单位时间，第三台需要7单位时间。
int N：表示有N个人需要用咖啡机制作咖啡，每人一杯，同时，假设制作完咖啡后，喝咖啡时间为0，一口闷。
int a：表示用洗碗机洗一个咖啡杯需要的时间，串行运行。
int b：表示咖啡杯也可以不洗，自然晾干的时间，咖啡杯要么洗，要么晾干。
现在，请你求出这N个人从开始用咖啡杯制作咖啡到杯子洗好或者晾干的最少时间？

思路分析

此题的总体时间，其实分成两部分，第一部分是制作咖啡的时间，第二部分是洗咖啡杯的时间。可以把这两部分时间分开，先来考虑制作咖啡的时间。
问题一：怎么能让N个人制作完咖啡的时间最短呢？
首先，肯定是让这几台咖啡机同时运行，那么，怎么能让他们一直工作。没有等待的现象？这就是一个经典的贪心算法思想，对吧？
贪心算法尝试：我们统计每台咖啡机的最早结束时间，让每台咖啡机，一旦结束，就立刻开始生产下一个人的咖啡，因此，我们的贪心策略是：统计每台咖啡机最早空闲时间，然后对最早空闲时间排序，每次让最早结束的咖啡机先服务。
如何实现上述贪心算法？我们可以创建一个小根堆，然后，小根堆根据最早结束时间排序，每次弹出最早结束的咖啡机，然后，生产一杯咖啡后，更新该咖啡机的结束时间后，再进入小根堆，重新排序，最终输出一个数组，就是N个人的最早喝完咖啡的时间。
问题二：怎么实现洗杯子的时间最短？
从问题一，我们可以拿到每个人的最早喝完咖啡的时间，在此基础上，每个杯子可以选择用洗碗机洗或者自己晾干。对于一个任意的咖啡杯，首先，洗碗机是否空闲，以及何时能空闲出来，不确定，同时，每个咖啡杯最早喝完的时间也不确定，因此，这个问题用贪心算法比较难解决。此时，只能考虑暴力一些的方法，用暴力递归尝试，每个咖啡杯递归使用洗碗机和晾干两种策略，然后递归选择时间较小的，就是结果。

代码

//比较器
class MyComparator implements Comparator<CoffeeMachine>{
    @Override
    public int compare(CoffeeMachine o1, CoffeeMachine o2) {
        return o1.allTime-o2.allTime;
    }
}

//小根堆中传输的数据结构，time：咖啡机的制作一个需要的时间，alltime：当前累计时间
class CoffeeMachine{
    int time;
    int allTime;
    public CoffeeMachine(int time){
        this.time=time;
        allTime=time;
    }
}

    //贪心算法实现制作咖啡
    public static int f2(int[] arr, int N,int a,int b){
        //小根堆
        PriorityQueue<CoffeeMachine> queue=new PriorityQueue<CoffeeMachine>(new MyComparator());
        //返回的是N个人最早制作完咖啡的数组
        int[] finishTime=new int[N];
        for (int i = 0; i < arr.length; i++) {
            queue.add(new CoffeeMachine(arr[i]));
        }
        CoffeeMachine coffeeMachine;
        for (int i = 0; i < N; i++) {
            coffeeMachine= (CoffeeMachine) queue.poll();
            finishTime[i]=coffeeMachine.allTime;
            coffeeMachine.allTime=coffeeMachine.allTime+coffeeMachine.time;
            queue.add(coffeeMachine);
        }
        return f3(finishTime,a,b,0,0);
    }

    //洗碗机与晾干的递归方法
    public static int f3(int[] finishTime,int a,int b,int index,int machineTime){
        if(index==finishTime.length-1){
            return Math.min(Math.max(finishTime[index],machineTime)+a,finishTime[index]+b);
        }
        //当前选择使用洗碗机,这个杯子需要的时间
        int wash=Math.max(finishTime[index],machineTime)+a;
        //后续的所有清洁杯子时间
        int next1=f3(finishTime,a,b,index+1,machineTime+a);
        //因为当前杯子的清洁时间是有可能比后面还慢，因此，选择两者中的较大值
        int p1=Math.max(wash,next1);

        //当前使用晾干
        int dry=finishTime[index]+b;
        //后续的所有清洁杯子时间
        int next2=f3(finishTime,a,b,index+1,machineTime);
        //因为当前杯子的清洁时间是有可能比后面还慢，因此，选择两者中的较大值
        int p2=Math.max(dry,next2);
        //返回两种选择策略的较小值
        return Math.min(p1,p2);
    }