题意：给n个医生，这些医生有一个上班时间，然后给一些病人，病人有一个到达的时间，以及一些诊断，诊断有property（优先级）和duration（诊断时间）这两个属性，每个病人可能要诊断多次，最后问每个病人的全部疗程完成离开医院的时间是多少。
分析：用优先队列存储诊断，病人，然后模拟一个诊断过程，完成病人的个数等于病人数的时候就结束。具体看代码吧。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <queue> #include <cstdlib> using namespace std; #define N 100102 #define M 22 struct treat { int tim,ind; treat(int _tim,int _ind):tim(_tim),ind(_ind){} treat(){} bool operator <(const treat& a)const { return tim > a.tim; } }; struct node { int x,y; node(int _x,int _y):x(_x),y(_y){} node(){} }; struct Patient { int id,pro,arrtim; Patient(int _id,int _pro,int _arrtim):id(_id),pro(_pro),arrtim(_arrtim){} Patient(){} bool operator <(const Patient& a)const { if(a.pro == pro) return arrtim > a.arrtim; return pro < a.pro; } }; priority_queue<treat> T; priority_queue<Patient> P; vector<node> pat[506],ans; int arrive[506],treated[506]; int cmp(node ka,node kb) { if(ka.x == kb.x) return ka.y < kb.y; return ka.x < kb.x; } int main() { int n,Tim,a,b,Pcnt,cs = 1; int i,j; while(scanf("%d%d",&n,&Tim)!=EOF && (n+Tim)) { Pcnt = 0; ans.clear(); while(scanf("%d",&arrive[Pcnt]) && arrive[Pcnt] != -1) { pat[Pcnt].clear(); while(scanf("%d%d",&a,&b) && (a+b)) //property,duration pat[Pcnt].push_back(node(a,b)); Pcnt++; } while(!T.empty()) T.pop(); while(!P.empty()) P.pop(); for(i=0;i<n;i++) //n个医生准备 T.push(treat(Tim,-1)); for(i=0;i<Pcnt;i++) T.push(treat(arrive[i],i)); //编号i int doctor = 0; memset(treated,-1,sizeof(treated)); int pcnt = 0; while(pcnt < Pcnt) { int nowt = T.top().tim; while(!T.empty() && T.top().tim == nowt) { if(T.top().ind == -1) //空闲doctor doctor++; else { int pid = T.top().ind; treated[pid]++; if(treated[pid] >= pat[pid].size()) //全部疗程完成 { ans.push_back(node(nowt,arrive[pid])); pcnt++; } else P.push(Patient(pid,pat[pid][treated[pid]].x,arrive[pid])); } T.pop(); } while(!P.empty() && doctor) { int k = P.top().id; T.push(treat(nowt+pat[k][treated[k]].y,-1)); //此时空闲 T.push(treat(nowt+pat[k][treated[k]].y,k)); //或者继续诊断此病人 P.pop(); doctor--; } } sort(ans.begin(),ans.end(),cmp); printf("Case %d: ",cs++); for(i=0;i<ans.size();i++) printf("Patient %d released at clock = %d ",ans[i].y,ans[i].x); } return 0; }