团体程序设计天梯赛竞赛题--登顶题【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^4）n（≤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岁及以上老人、普通患者，分别存入按预约号降序排序的优先队列。医生叫号遵循优先级：优先呼叫当前时间段的预约患者；若无人等待，优先调度老人队列，无老人则调度普通队列。用标记数组记录已就诊患者，避免重复叫号，动态推进就诊时间，直至所有患者完成就诊。算法通过优先队列实现高效调度，线性模拟时间流程，完美适配题目规则与数据规模。

总结

核心逻辑：按时间模拟就诊流程，遵循当前预约号优先→高龄患者优先→普通患者优先的规则调度就诊。
关键操作：患者按到达时间排序、双优先队列分类候诊、时间逐段推进、标记已就诊状态。
效率保障：优先队列实现对数级调度效率，线性时间模拟，高效处理题目约束的患者规模。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;structPt{inta,b;string id;intag;};intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cin>>n;vector<Pt>arr(n);for(inti=0;i<n;++i){cin>>arr[i].a>>arr[i].b>>arr[i].id>>arr[i].ag;}sort(arr.begin(),arr.end(),[](constPt&x,constPt&y){returnx.a<y.a;});vector<Pt*>byB(n+1,nullptr);vector<bool>svd(n+1,false);autocmp=[](constPt*x,constPt*y){returnx->b>y->b;};priority_queue<Pt*,vector<Pt*>,decltype(cmp)>eQ(cmp),nQ(cmp);intt=1,idx=0,un=0;while(idx<n||un>0){if(un==0&&idx<n&&t<arr[idx].a){t=arr[idx].a;}while(idx<n&&arr[idx].a<=t){Pt*p=&arr[idx];byB[p->b]=p;if(p->ag>=80)eQ.push(p);elsenQ.push(p);++un;++idx;}Pt*sel=nullptr;if(t<=n&&byB[t]!=nullptr&&!svd[byB[t]->b]){sel=byB[t];}else{while(!eQ.empty()&&svd[eQ.top()->b])eQ.pop();if(!eQ.empty()){sel=eQ.top();eQ.pop();}else{while(!nQ.empty()&&svd[nQ.top()->b])nQ.pop();if(!nQ.empty()){sel=nQ.top();nQ.pop();}}}if(sel!=nullptr){svd[sel->b]=true;cout<<t<<" "<<sel->id<<'\n';--un;}++t;}return0;}