題目描述：給定一個數組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);
}
