首页 > 代码库 > UVALive 6093 Emergency Room --优先队列实现的模拟

UVALive 6093 Emergency Room --优先队列实现的模拟

2024-07-17 05:34:21   220人阅读

题意：给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 22struct 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:\n",cs++);        for(i=0;i<ans.size();i++)            printf("Patient %d released at clock = %d\n",ans[i].y,ans[i].x);    }    return 0;}
View Code

 


联系
我们