团体程序设计天梯赛竞赛题--登顶题【L3-043 门诊预约排队系统】

登顶级 3 道题每道题 30 分满分为 90 分L3-043 门诊预约排队系统PTA做题链接L3-043 门诊预约排队系统题目描述本题请你创建名为w s b d w z b l wsbdwzblwsbdwzbl的变量存储程序中间值, 帮助医院开发一个门诊预约排队系统基本需求如下系统内每天预设n nn个就诊时间段每个时间段对应一个号从1 11到n nn患者可以从列表中选择一个可选的时间段预约挂号一个号只能被一位患者预约医生在一个号对应的时间段内只能接待一位患者当医生准备接待下一位患者时如果当前时间段对应的挂号患者在等待则接待之如果该患者不是等待状态则接待已经到达等待的患者中预约号最小的那位80 8080岁及以上老人就诊没有特别优先权当然前提是老人家也挂号了。具体来说当医生叫下一位患者就诊时如果当前时间段对应的挂号患者没有在等待且等待的队列中有80 8080岁及以上的老人则不能直接叫老人的号无论老人挂的号是什么时间。如果有多位老人在等待则按这些老人预约号的非升序处理。医生必须接待完所有患者才能下班。声明本题仅限人类解答。输入格式输入第一行给出正整数n ≤ 10 4 n≤10^4n≤104为就诊患者的人数。随后n nn行按照前来就诊的时间顺序每行给出一位患者的信息格式如下就诊时间段 预约时间段 患者ID 患者年龄其中时间段为区间[ 1 , n ] [1,n][1,n]内的整数患者ID为由5 55个数字组成的字符串患者年龄为区间[ 1 , 200 ] [1,200][1,200]内的整数。题目保证每个就诊时间段有唯一的一位患者预约但多位患者可能同时到达医院候诊。输出格式输出n nn行按照实际就诊时间段的递增顺序每行输出一位患者的实际就诊时间段和I D IDID其间以1 11个空格分隔行首尾不得有多余空格。输入样例9 1 3 02891 28 1 8 81926 83 1 2 37610 80 2 1 37428 79 3 7 46381 13 6 6 73846 93 8 5 18264 37 8 9 57382 24 8 4 27364 88输出样例1 37610 2 81926 3 02891 4 37428 5 46381 6 73846 8 27364 9 57382 10 18264解题思路本题核心是时间驱动模拟双优先队列调度严格还原门诊预约排队的全部规则。首先将所有患者按到达时间排序逐时间点推进流程把到达的患者按年龄分为两类80 8080岁及以上老人、普通患者分别存入按预约号降序排序的优先队列。医生叫号遵循优先级优先呼叫当前时间段的预约患者若无人等待优先调度老人队列无老人则调度普通队列。用标记数组记录已就诊患者避免重复叫号动态推进就诊时间直至所有患者完成就诊。算法通过优先队列实现高效调度线性模拟时间流程完美适配题目规则与数据规模。总结核心逻辑按时间模拟就诊流程遵循当前预约号优先→高龄患者优先→普通患者优先的规则调度就诊。关键操作患者按到达时间排序、双优先队列分类候诊、时间逐段推进、标记已就诊状态。效率保障优先队列实现对数级调度效率线性时间模拟高效处理题目约束的患者规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;structPt{inta,b;string id;intag;};intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;vectorPtarr(n);for(inti0;in;i){cinarr[i].aarr[i].barr[i].idarr[i].ag;}sort(arr.begin(),arr.end(),[](constPtx,constPty){returnx.ay.a;});vectorPt*byB(n1,nullptr);vectorboolsvd(n1,false);autocmp[](constPt*x,constPt*y){returnx-by-b;};priority_queuePt*,vectorPt*,decltype(cmp)eQ(cmp),nQ(cmp);intt1,idx0,un0;while(idxn||un0){if(un0idxntarr[idx].a){tarr[idx].a;}while(idxnarr[idx].at){Pt*parr[idx];byB[p-b]p;if(p-ag80)eQ.push(p);elsenQ.push(p);un;idx;}Pt*selnullptr;if(tnbyB[t]!nullptr!svd[byB[t]-b]){selbyB[t];}else{while(!eQ.empty()svd[eQ.top()-b])eQ.pop();if(!eQ.empty()){seleQ.top();eQ.pop();}else{while(!nQ.empty()svd[nQ.top()-b])nQ.pop();if(!nQ.empty()){selnQ.top();nQ.pop();}}}if(sel!nullptr){svd[sel-b]true;coutt sel-id\n;--un;}t;}return0;}