济南传承网站建设李聪,无锡建站方案,oa软件是做什么的,住房和城乡建设部建造师网站题目 题有点难#xff0c;但还挺有趣 有一个咖啡机数组arr[]#xff0c;其中arr[i]代表每一个咖啡机冲泡咖啡所需的时间#xff0c;有整数N#xff0c;代表着准备冲咖啡的N个人#xff08;假设这个人拿到咖啡后喝完的时间为0#xff0c;拿手里咖啡杯即变空#xff09;但还挺有趣 有一个咖啡机数组arr[]其中arr[i]代表每一个咖啡机冲泡咖啡所需的时间有整数N代表着准备冲咖啡的N个人假设这个人拿到咖啡后喝完的时间为0拿手里咖啡杯即变空有一台洗咖啡杯的机器一次只能洗一只杯子每次洗咖啡杯消耗的时间为a如果咖啡杯自己挥发变干净消耗的时间是b返回从排队开始到所有咖啡杯变干净的最短时间。
分析
根据题意梳理后可得知每台咖啡机冲泡咖啡是并行操作的但是单独的咖啡机自己是只有等当前的咖啡冲泡完成后才可冲泡下一杯是串行操作的。洗咖啡杯的机器消耗时间为a但是要等咖啡冲泡完成后才可进行清洗。举例1号咖啡机冲泡1杯咖啡时间为2分钟从0时间点开始冲泡一杯咖啡2分钟时间点结束。那么洗咖啡杯的机器是在2分钟的时间点开始工作在2 a时间点工作完成才可进行下一只咖啡杯的清洗。需要注意的是如果咖啡杯1和2都选择清洗但是1号咖啡杯是9时间点喝完2号咖啡杯是6时间点喝完则2号咖啡杯在清洗时开始的时间点是 9 a是根据上一直需要清洗的咖啡杯的时间来决定的。咖啡杯自己挥发是并行操作并且变干净的时间都是b。
暴力递归 依然是从暴力递归开始分析并从暴力递归转换成动态规划但是在暴力递归之前先将这道题拆解成2道题来看。 首先是根据咖啡机数组arr和准备冲咖啡的人数N来实现一个模拟排队的功能。作用是能够获取到每个人能够最快获取到咖啡的时间点。
模拟排队 模拟排队的功能实现用到了PriorityQueue并且自己实现了咖啡机的比较规则根据PriorityQueue的特性让效率最快的咖啡机始终在最上面并进行使用。其中0,1表示当前咖啡机可用时间点为0冲泡一杯咖啡时间为1。
解释一下上边的图 咖啡机数组arr{1,3,7}代表着0号咖啡机冲泡一杯咖啡所需时间为11号咖啡机所需时间为32号咖啡机所需时间为7。开始时咖啡可用时间都从0时间点开始。一共有5个人排队冲咖啡。 根据咖啡机冲泡一杯所需时间 和 咖啡机下一次可用时间 来实现咖啡机的效率最大化。
所以
第一个人过来时会去0号咖啡机冲咖啡此时咖啡机在1时间点冲完并且咖啡机下次可用时间点为1。第二个人过来时0号咖啡机可用时间点为1冲泡一杯咖啡所需时间为1 1 1 2 小于1号咖啡机冲泡一杯的时间3所以还是会选择0号咖啡机冲泡咖啡。第三个人过来时0号咖啡机会在2时间点可用冲泡一杯咖啡时间依然是1但是此时1号咖啡机可用时间点是0冲泡咖啡的时间是3。此时0号咖啡机和1号咖啡机冲泡一杯咖啡结束的时间点相同用谁都可以我们假设用1号咖啡机用完后1号咖啡机可用时间点为3**根据PriorityQueue的特性0号咖啡机又会排到上面 **。所以第四个人、第五个人过来都会选择0号咖啡机。
代码
public static class Machine {// 咖啡机可以工作的时间点int timePoint;//泡一杯咖啡所需时间int workTime;public Machine(int timePoint, int workTime) {this.timePoint timePoint;this.workTime workTime;}}//自定义比较器public static class MachineComparator implements ComparatorMachine {Overridepublic int compare(Machine o1, Machine o2) {return (o1.timePoint o1.workTime) - (o2.timePoint o2.hashCode());}}public static int forceMake(int[] arr, int N, int a, int b) {PriorityQueueMachine heap new PriorityQueue(new MachineComparator());//初始化时填充heapfor (int i 0; i arr.length; i) {heap.add(new Machine(0, arr[i]));}//每个人最快可以喝到咖啡的数组int[] drinks new int[N];for (int i 0; i N; i) {//获取堆顶的咖啡机元素Machine curMachine heap.poll();//咖啡机下次可用时间curMachine.timePoint curMachine.workTime;//什么时间可以喝到咖啡drinks[i] curMachine.timePoint;//再次压入堆中heap.add(curMachine);}//process方法是递归方法求出咖啡杯变干净的最少时间。return process(drinks, a, b, 0, 0);}第一个模拟排队的问题解决了接下来就是正式的暴力递归。 暴力递归方法返回drinks[index…]位置变干净的最小时间。 所以此时base case也可以确定下来了 index drinks.length。 而每只杯子可以选择清洗也可以选择挥发变干净。 所以在递归向下传递时需要注意清洗咖啡杯机器的可用时间的变化。
代码 代码中在向下传递时如果我选择了清洗则机器的可用时间是会向后延长的如果选择了风干也是要根据咖啡杯的可用时间来取最大值的木桶原理最后在清洗和风干中取小的。 //drinks: 每个人喝到咖啡的最短时间//wash : 用洗咖啡杯机器洗一只咖啡杯的时间// air : 空气挥发一杯咖啡杯的时间//index: 第几只杯子//free : 下一次洗咖啡杯机器可用时间public static int process(int[] drink, int wash, int air, int index, int free) {//没有杯子了if (index drink.length) {return 0;}//选择洗int selfClean1 Math.max(drink[index], free) wash;//向下传递下一只杯子清洗干净的时间此时清洗咖啡杯机器的可用时间为selfClean1int restClean1 process(drink, wash, air, index 1, selfClean1);//木桶原理因为选择了清洗所以要看当前杯子selfClean和下一个杯子restClean那个时间更大选择哪个int p1 Math.max(selfClean1, restClean1);// 选择风干int selfClean2 drink[index] air;//free依然是free清洗咖啡杯机器的时间没有变化。int restClean2 process(drink, wash, air, index 1, free);//同理int p2 Math.max(selfClean2, restClean2);//在风干和清洗中选择一个最小的。return Math.min(p1, p2);}动态规划 根据暴力递归中的代码来改写动态规划从暴力递归代码中可以看出可变参数是数组下标index和清洗咖啡杯机器的freeTime。并且index的范围是 0 ~ drinks.length需要注意的是freeTime和之前题的可变参数范围不同。这道题中freeTime的时间范围并不好确定需要根据具体的业务来算出来按照drinks中最大喝完咖啡的时间 清洗一杯咖啡杯的时间。 所以dp[][] 初始化时可以确定范围 dp[N 1][maxFree]。 还需要注意的一点是因为在遍历dp填充值的时候内循环是遍历maxFree而变量free是可以无限逼近maxFree的所以在计算restClean时需要进行判断否则很可能会有数组下标越界的情况。 而在暴力递归过程中无论怎么清洗咖啡杯时间都不可能大于maxFree。所以如果计算的selfClean1变量再加完 wash后如果 maxFree则证明是无效的。在实际过程中不存在这种情况。break。这个值不用填充。
public static int dp(int[] drinks, int wash, int air) {int N drinks.length;int maxFree 0;for (int i 0; i N; i) {maxFree Math.max(maxFree, drinks[i]) wash;}int[][] dp new int[N 1][maxFree 1];for (int index N - 1; index 0; index--) {for (int free 0; free maxFree; free) {int selfClean1 Math.max(drinks[index], free) wash;if (selfClean1 maxFree){break;}int restClean1 dp[index 1][selfClean1];int p1 Math.max(selfClean1, restClean1);int selfClean2 drinks[index] air;int restClean2 dp[index 1][free];int p2 Math.max(selfClean2, restClean2);dp[index][free] Math.min(p1, p2);}}return dp[0][0];}完整代码 public static class Machine {// 咖啡机下一次可以工作的时间int timePoint;//泡一杯咖啡所需时间int workTime;public Machine(int timePoint, int workTime) {this.timePoint timePoint;this.workTime workTime;}}public static class MachineComparator implements ComparatorMachine {Overridepublic int compare(Machine o1, Machine o2) {return (o1.timePoint o1.workTime) - (o2.timePoint o2.hashCode());}}public static int minTime(int[] arr, int N, int a, int b) {PriorityQueueMachine heap new PriorityQueue(new MachineComparator());for (int i 0; i arr.length; i) {heap.add(new Machine(0, arr[i]));}int[] drinks new int[N];for (int i 0; i N; i) {Machine curMachine heap.poll();drinks[i] curMachine.timePoint;curMachine.timePoint curMachine.workTime;heap.add(curMachine);}return process(drinks, a, b, 0, 0);}//drinks: 每个人喝咖啡的最短时间//wash : 用洗咖啡杯机器洗一只咖啡杯的时间// air : 空气挥发一杯咖啡杯的时间//index: 第几只杯子//free : 下一次洗咖啡杯机器可用时间public static int process(int[] drink, int wash, int air, int index, int free) {//没有杯子了if (index drink.length) {return 0;}//选择洗int selfClean1 Math.max(drink[index], free) wash;int restClean1 process(drink, wash, air, index 1, selfClean1);int p1 Math.max(selfClean1, restClean1);// 选择风干int selfClean2 drink[index] air;int restClean2 process(drink, wash, air, index 1, free);int p2 Math.max(selfClean2, restClean2);return Math.min(p1, p2);}public static int minTime2(int[] arr, int N, int a, int b) {PriorityQueueMachine heap new PriorityQueue(new MachineComparator());for (int i 0; i arr.length; i) {heap.add(new Machine(0, arr[i]));}int[] drinks new int[N];for (int i 0; i N; i) {Machine curMachine heap.poll();drinks[i] curMachine.timePoint;curMachine.timePoint curMachine.workTime;heap.add(curMachine);}return dp(drinks, a, b);}public static int dp(int[] drinks, int wash, int air) {int N drinks.length;int maxFree 0;for (int i 0; i N; i) {maxFree Math.max(maxFree, drinks[i]) wash;}int[][] dp new int[N 1][maxFree 1];for (int index N - 1; index 0; index--) {for (int free 0; free maxFree; free) {int selfClean1 Math.max(drinks[index], free) wash;if (selfClean1 maxFree){break;}int restClean1 dp[index 1][selfClean1];int p1 Math.max(selfClean1, restClean1);int selfClean2 drinks[index] air;int restClean2 dp[index 1][free];int p2 Math.max(selfClean2, restClean2);dp[index][free] Math.min(p1, p2);}}return dp[0][0];}
文章转载自： http://www.morning.lznfl.cn.gov.cn.lznfl.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.zrjzc.cn.gov.cn.zrjzc.cn http://www.morning.c7512.cn.gov.cn.c7512.cn http://www.morning.dnbhd.cn.gov.cn.dnbhd.cn http://www.morning.skrww.cn.gov.cn.skrww.cn http://www.morning.bfnbn.cn.gov.cn.bfnbn.cn http://www.morning.fmqw.cn.gov.cn.fmqw.cn http://www.morning.hyyxsc.cn.gov.cn.hyyxsc.cn http://www.morning.mqzcn.cn.gov.cn.mqzcn.cn http://www.morning.bqwsz.cn.gov.cn.bqwsz.cn http://www.morning.wgtr.cn.gov.cn.wgtr.cn http://www.morning.jbtzx.cn.gov.cn.jbtzx.cn http://www.morning.qmpbs.cn.gov.cn.qmpbs.cn http://www.morning.xoaz.cn.gov.cn.xoaz.cn http://www.morning.jfnbh.cn.gov.cn.jfnbh.cn http://www.morning.qklff.cn.gov.cn.qklff.cn http://www.morning.znsyn.cn.gov.cn.znsyn.cn http://www.morning.tslfz.cn.gov.cn.tslfz.cn http://www.morning.ktyww.cn.gov.cn.ktyww.cn http://www.morning.hhfwj.cn.gov.cn.hhfwj.cn http://www.morning.cyyhy.cn.gov.cn.cyyhy.cn http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.prgdy.cn.gov.cn.prgdy.cn http://www.morning.zdsqb.cn.gov.cn.zdsqb.cn http://www.morning.mfqmk.cn.gov.cn.mfqmk.cn http://www.morning.lwtld.cn.gov.cn.lwtld.cn http://www.morning.mwmtk.cn.gov.cn.mwmtk.cn http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.qhrlb.cn.gov.cn.qhrlb.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.ctlbf.cn.gov.cn.ctlbf.cn http://www.morning.smwlr.cn.gov.cn.smwlr.cn http://www.morning.cjmmn.cn.gov.cn.cjmmn.cn http://www.morning.ngcbd.cn.gov.cn.ngcbd.cn http://www.morning.lwsct.cn.gov.cn.lwsct.cn http://www.morning.sfmqm.cn.gov.cn.sfmqm.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.lgmgn.cn.gov.cn.lgmgn.cn http://www.morning.thntp.cn.gov.cn.thntp.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn http://www.morning.vuref.cn.gov.cn.vuref.cn http://www.morning.xqgtd.cn.gov.cn.xqgtd.cn http://www.morning.rwjh.cn.gov.cn.rwjh.cn http://www.morning.fnpmf.cn.gov.cn.fnpmf.cn http://www.morning.mjpgl.cn.gov.cn.mjpgl.cn http://www.morning.rmrcc.cn.gov.cn.rmrcc.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.tgmwy.cn.gov.cn.tgmwy.cn http://www.morning.rqkck.cn.gov.cn.rqkck.cn http://www.morning.ykwbx.cn.gov.cn.ykwbx.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.080203.cn.gov.cn.080203.cn http://www.morning.lftpl.cn.gov.cn.lftpl.cn http://www.morning.hongjp.com.gov.cn.hongjp.com http://www.morning.xwlmr.cn.gov.cn.xwlmr.cn http://www.morning.hhpbj.cn.gov.cn.hhpbj.cn http://www.morning.rycbz.cn.gov.cn.rycbz.cn http://www.morning.fglth.cn.gov.cn.fglth.cn http://www.morning.sjwiki.com.gov.cn.sjwiki.com http://www.morning.wjndl.cn.gov.cn.wjndl.cn http://www.morning.clzly.cn.gov.cn.clzly.cn http://www.morning.drzkk.cn.gov.cn.drzkk.cn http://www.morning.wqbzt.cn.gov.cn.wqbzt.cn http://www.morning.cwwbm.cn.gov.cn.cwwbm.cn http://www.morning.prhqn.cn.gov.cn.prhqn.cn http://www.morning.jhswp.cn.gov.cn.jhswp.cn http://www.morning.cfnsn.cn.gov.cn.cfnsn.cn http://www.morning.smtrp.cn.gov.cn.smtrp.cn http://www.morning.ntyanze.com.gov.cn.ntyanze.com http://www.morning.pmmrb.cn.gov.cn.pmmrb.cn http://www.morning.xirfr.cn.gov.cn.xirfr.cn http://www.morning.0small.cn.gov.cn.0small.cn http://www.morning.pmnn.cn.gov.cn.pmnn.cn http://www.morning.wyrsn.cn.gov.cn.wyrsn.cn http://www.morning.drndl.cn.gov.cn.drndl.cn http://www.morning.cnlmp.cn.gov.cn.cnlmp.cn http://www.morning.ychoise.com.gov.cn.ychoise.com http://www.morning.kzcfr.cn.gov.cn.kzcfr.cn http://www.morning.ytbr.cn.gov.cn.ytbr.cn
