2023年天梯赛真题解析L2-2（优先级队列）

L2-046 天梯赛的赛场安排题目链接https://pintia.cn/problem-sets/994805046380707840/exam/problems/type/7?problemSetProblemId1649748772841508873page1题目分析本题的考点是结构体优先级队列因为每个学校包含的信息较多用结构体来存储比较方便用优先级队列可以快速找到尚未安排赛场的最多的队员人数好进行分配具体看解法代码#includebits/stdc.husingnamespacestd;//总结题目包含的信息比较多我们可以创建结构体来记录数据structschool{string name;inttotal_stu;intteacher;intres_stu;//剩余的需要安排的学生数量};intmain(){intn,c;cinnc;vectorstringsl_name;mapstring,intans;//存最后的答案autocmp[](structschoola,structschoolb){returna.res_stub.res_stu;};vectorintroom;//这里我们还需要一个变量来存储剩余空位数priority_queueschool,vectorschool,decltype(cmp)pq(cmp);for(inti0;in;i){string s;cins;sl_name.push_back(s);intx;cinx;pq.push({s,x,0,x});}while(!pq.empty()){school currentpq.top();pq.pop();if(current.res_stu0){ans[current.name]current.teacher;continue;//如果为0就一直删,同时存一下数据}if(current.res_stuc){current.res_stu-c;current.teacher;room.push_back(0);pq.push(current);//这里再重新加入优先级队列}else{boolfindfalse;for(autospace:room){//这里一定要用引用if(spacecurrent.res_stu){current.res_stu0;space-current.res_stu;current.teacher;findtrue;break;}}if(!find){room.push_back(c-current.res_stu);current.teacher;current.res_stu0;}pq.push(current);}}for(autos:sl_name){couts ans[s]endl;}coutroom.size();return0;}