关于流水下调度之前上课，高老师讲了（一台和两台机器的调度问题，不过都是一次加工完成的，如果是这种情况就只需要每次挑加工时间最短的就可以了）。但是这题较之要难一点：一件物品加工两次：一件物品粗加工后，才能到第二个机器进行深加工。因此计算时间的时候借助画线段来分析思路比较清晰。
思路：先把所有物品分为两类，一类是粗加工比深加工时间短的，这个集合内元素的排序按粗加工的时间从小到大排序。另一类是深加工时间比粗加工时间长的，这个集合内的元素按深加工的时间从大到小排列。计算时先计算第一类的时间，再进行第二类的时间。
正确性：因为分三种情况进行分类讨论，所以对三种情况分别用剪切-粘贴的方法进行验证。不过讨论和考虑时要注意的是，只用当一件物品完成粗加工才可深加工，这时m2处于等待的时间。
计算的时候当times1>times2时，times2要和times1对其，这样做才可以补上m2等待的时间。
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
int n,m1,m2,times1,times2,times,wait,temp,temp2;struct work{int mt1,mt2;work(int mm1,int mm2):mt1(mm1),mt2(mm2){}
};struct cmp1{bool operator()(work &a,work &b){return a.mt1>b.mt1;}
};struct cmp2{bool operator()(work &a,work &b){return a.mt2<b.mt2;}
};int main(){while(scanf("%d",&n)!=EOF){priority_queue<work,std::vector<work>,cmp1> q1;///m1的时间小于m2的时间的集合priority_queue<work,std::vector<work>,cmp2> q2;///除了第一集合外的另一个集合times1=times2=times=0;for(int i=0;i<n;i++){scanf("%d%d",&m1,&m2);if(m1<m2)q1.push(work(m1,m2));///3 7elseq2.push(work(m1,m2));///2 1\1 1\4 2}work w=work(0,0);if(!q1.empty()){w=q1.top();temp=w.mt1;temp2=w.mt2;times1+=temp;///781times2+=temp;///781q1.pop();}while(!q1.empty()){work w=q1.top();q1.pop();temp=w.mt1;times2+=temp2;///781+1374times1+=temp;///781+2452if(times1>times2)times2=times1;temp2=w.mt2;///6678}times2+=temp2;///781+2452+6678if(!q2.empty()){w=q2.top();q2.pop();times1+=w.mt1;///781+2452+5736temp2=w.mt2;///3793}while(!q2.empty()){w=q2.top();q2.pop();times1+=w.mt1;///781+2452+6678+2457 781+2452+6678+3793+935times2+=temp2;///781+2452+6678+3793 781+2452+6678+3793+2045if(times1>times2)times2=times1;temp2=w.mt2;}times2+=temp2;times+=max(times2,times1);printf("%d\n",times);}return 0;
}