题目描述：给定一个数组arr，arr[i]代表第i号咖啡机泡一杯咖啡的时间，给定一个正数N，表示N个人在等着咖啡机，每台咖啡机只能一个一个的泡咖啡，其次，只有一台咖啡机可以洗杯子，一次只能洗一个杯子，时间耗费a，洗完才能洗下一杯子，每个咖啡杯也可以自己挥发干净，时间耗费b，咖啡杯可以并行挥发，假设所有人拿到咖啡之后立刻喝完，返回从开始等到所有咖啡机变干净的最短时间，有4个参数，arr, N, a, b。
way：
//drinks是每人喝完咖啡的最早时间，也是杯子们可以开始洗的最早时间
//wash 洗一个杯子需要的时间（串行）
//air 挥发干净的时间（并行）
//washLine 洗杯子的机器可以洗的时间点(也就是洗杯子的咖啡机空闲的时间点）
//index之前的杯子都洗过了，drinks[index...]的杯子都变干净的最早结束时间#include<iostream>
#include<vector>
#include<queue>
using namespace std;struct Machine
{//机器工作的时间点int timePoint;//泡一杯咖啡的时间int workTime;Machine(int timePoint, int workTime){this->timePoint = timePoint;this->workTime = workTime;}
};struct comp
{bool operator()(Machine *a, Machine *b){return a->timePoint+a->workTime < b->timePoint+b->workTime;}
};//drinks是每人喝完咖啡的最早时间，也是杯子们可以开始洗的最早时间
//wash 洗一个杯子需要的时间（串行）
//air 挥发干净的时间（并行）
//washLine 洗杯子的机器可以洗的时间点(也就是洗杯子的咖啡机空闲的时间点）
//index之前的杯子都洗过了，drinks[index...]的杯子都变干净的最早结束时间
int process(vector<int>drinks, int index, int wash, int air, int washLine)
{if(index == drinks.size()){return 0;}//index号杯子决定洗int time1=max(drinks[index], washLine)+wash;int time2=process(drinks, index+1, wash, air, time1);int p1=max(time1, time2);//index号杯子决定挥发,咖啡机不用等int time3=drinks[index]+air;int time4=process(drinks, index+1, wash, air, washLine);int p2=max(time3,time4);return min(p1,p2);
}int minTime(vector<int>arr, int N, int a, int b)
{//小根堆priority_queue<Machine*,vector<Machine*>, comp>que;vector<int>drinks(N);for(int i=0; i<arr.size(); i++){que.push(new Machine(0,arr[i]));}//N个人最早喝完咖啡的时间存到drinks数组中for(int i=0; i<N; i++){Machine *machine = que.top();que.pop();machine->timePoint+=machine->workTime;drinks[i]=machine->timePoint;que.push(machine);}return process(drinks, 0, a, b, 0);
}way2：改dp。
//index从大往小填
int minTimeDp(vector<int>drinks, int wash, int air)
{//找到washLine的最大值是多少int nMax=0;for(int i=0; i<drinks.size(); i++){//每个杯子都洗的最大时间,如果还没喝,等喝完再洗,如果咖啡机在洗上一个杯子,等上一个杯子洗完再洗nMax=max(nMax+wash, drinks[i]+wash);}int N=drinks.size();vector<vector<int>>dp(N+1,vector<int>(nMax+1));for(int index=N-1; index>=0; index--){for(int free=0; free<=nMax; free++){int time1=max(drinks[index], free)+wash;if(time1>nMax){//这种情况没可能吧break;}//index号杯子决定洗int time2=dp[index+1][time1];int p1=max(time1, time2);//index号杯子决定挥发int time3=drinks[index]+air;int time4=dp[index+1][free];int p2=max(time3, time4);dp[index][free]=min(p1,p2);}}return dp[0][0];
}int minTime2(vector<int>arr, int N, int a, int b)
{priority_queue<Machine*,vector<Machine*>, comp>que;vector<int>drinks(N);for(int i=0; i<arr.size(); i++){que.push(new Machine(0,arr[i]));}//N个人最早喝完咖啡的时间存到drinks数组中for(int i=0; i<N; i++){Machine *machine = que.top();que.pop();machine->timePoint+=machine->workTime;drinks[i]=machine->timePoint;que.push(machine);}return minTimeDp(drinks, a,b);
}
