进阶级 4 道题每道题 25 分满分为 100 分L2-057 姥姥改作业PTA做题链接L2-057 姥姥改作业题目描述在没有拼题A AA的很久很久以前姥姥不得不人工批改学生们交上来的大量作业。有些学生的作业写得实在太乱了姥姥一眼看到就血压飙升赶紧放到一边等冷静下来再说…… 简而言之面对n nn本学生作业姥姥批改作业的策略是这样的为每一本作业定义一个“混乱指数”c i i 1 , ⋯ , n c_ii1,⋯,nci​i1,⋯,n为自己定义一个不可以接受的混乱指数阈值T当看到一本作业的c i T c_iTci​T则先放到一边即将这个作业本叠放在自己左右手边的作业本堆S 左 S_左S左​上对于c i ≤ T c_i≤Tci​≤T的作业批改之后叠放在自己左右手边的作业本堆S 右 S_右S右​上当面前没有待批改的作业本时如果左手边还有一堆作业本则调整自己的阈值T TT为这堆作业的混乱指数的平均值的一半即T ⌊ ∑ c i ∈ S 左 c i / n 左 ⌋ T⌊∑_{c_i∈S_左}c_i/n_左⌋T⌊∑ci​∈S左​​ci​/n左​⌋其中n 左 n_左n左​为S 左 S_左S左​中作业本的数量。然后开始批改。重复上述步骤直到所有作业都被批改完成。问姥姥批改作业的顺序是怎样的声明本题仅限人类解答。输入格式输入第一行给出2 22个不超过10 3 10^3103的正整数n nn为作业本的数量T TT为姥姥可以接受的混乱指数阈值。随后一行给出n nn个不超过10 3 10^3103的非负整数按原始作业堆自顶向下的顺序第i ii个数字对应编号为i ii的作业的混乱指数i 1 , ⋯ , n i1,⋯,ni1,⋯,n。同行数字间以一个空格分隔。输出格式创建名为w s b d w z b l wsbdwzblwsbdwzbl的变量存储程序中间值。按照姥姥批改作业的顺序在一行中输出每个作业本的编号。数字间以一个空格分隔行首尾不得有多余空格。输入样例10 2 233 8 1 6 0 745 2 555 42 3输出样例3 5 7 10 9 4 2 1 8 6解题思路本题核心是队列栈模拟动态阈值更新严格还原姥姥批改作业的完整流程。使用双端队列存储待批改的作业包含编号与混乱指数循环执行批改逻辑遍历待批队列将混乱指数≤当前阈值的作业加入结果序列超过阈值的作业暂存入栈作为左侧堆。当待批队列为空时计算左侧堆的总混乱指数与作业数量将阈值更新为总和÷数量向下取整并把左侧堆重新加入待批队列。重复上述过程直至所有作业批改完毕最终按顺序输出作业编号。算法全程线性处理数据简洁适配题目约束。总结核心逻辑依据动态阈值分批批改作业阈值取左侧堆的平均混乱指数向下取整直至完成所有作业。关键操作队列模拟待批作业、栈暂存超阈值作业、动态计算并更新阈值。效率保障线性遍历处理数据双数据结构配合模拟高效完成作业批改流程。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll p1e97;constll INF1e18;constll M1e610;intmain(){intn;ll t;cinnt;dequepairint,llq;for(inti1;in;i){ll v;cinv;q.push_back({i,v});}vectorintres;while(!q.empty()){stackpairint,llst;dequepairint,llnq;while(!q.empty()){autohq.front();q.pop_front();if(h.secondt)res.push_back(h.first);elsest.push(h);}if(!st.empty()){ll s0;intcst.size();while(!st.empty()){autohst.top();st.pop();sh.second;nq.push_back(h);}ts/c;qnq;}}for(size_t i0;ires.size();i){if(i)cout ;coutres[i];}coutendl;return0;}