L2-041 插松枝

23年刚进新生群就听学长们说过这道题的毒瘤25年天梯赛选拔赛遇到它没写出来时至今日再次尝试终于使用双端队列模拟松枝将它写了出来L2-041 插松枝分数 25作者 陈越单位 浙江大学人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上做成大大小小的松枝。他们的工作流程并不是这样的每人手边有一只小盒子初始状态为空。每人面前有用不完的松枝干和一个推送器每次推送一片随机型号的松针片。工人首先捡起一根空的松枝干从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的就从推送器上取一片松针。将这片松针插到枝干的最下面。工人在插后面的松针时需要保证每一步插到一根非空松枝干上的松针片不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求就取之插好否则去推送器上取一片。如果推送器上拿到的仍然不满足要求就把拿到的这片堆放到小盒子里继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的工人每次只能取出最上面即最后放入的一片。当下列三种情况之一发生时工人会结束手里的松枝制作开始做下一个1小盒子已经满了但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里推送器上取到的松针压回推送器开始下一根松枝的制作。2小盒子中最上面的松针不满足要求但推送器上已经没有松针了。此时将手中的松枝放到成品篮里开始下一根松枝的制作。3手中的松枝干上已经插满了松针将之放到成品篮里开始下一根松枝的制作。现在给定推送器上顺序传过来的 N 片松针的大小以及小盒子和松枝的容量请你编写程序自动列出每根成品松枝的信息。输入格式输入在第一行中给出 3 个正整数N≤103为推送器上松针片的数量M≤20为小盒子能存放的松针片的最大数量K≤5为一根松枝干上能插的松针片的最大数量。随后一行给出 N 个不超过 100 的正整数为推送器上顺序推出的松针片的大小。输出格式每支松枝成品的信息占一行顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔行首尾不得有多余空格。输入样例8 3 420 25 15 18 20 18 8 5输出样例20 1520 18 18 825 5代码长度限制16 KBJava (javac)时间限制500 ms内存限制64 MB其他编译器时间限制400 ms内存限制64 MB栈限制8192 KB#includebits/stdc.h using namespace std; int main(){ int n,m,k;cinnmk; stackintbox; dequeintdq; vectorinta(n1); int pos1; for(int i1;in;i) cina[i]; /* 这道题我的想法是不能贪一次循环只操作一片 细水长流这一块。。 */ while(posn||box.size()){//当有松枝可插时就一直操作 /* 如果此时推送器上面没了只剩box判断box顶 如果顶合法就留给下一步操作 如果顶不合法那么是时候换松枝了 将我的deque清空 */ if(posndq.size()dq.back()box.top()){ while(dq.size()){ coutdq.front(); dq.pop_front(); if(dq.size()) cout ; else coutendl; } } /* 判断box顶是不是能插 能插就插到松枝上每一次插到松枝上我都判断是不是满了 如果满了我就提前清空换松枝 */ if(box.size()(dq.size()0||box.top()dq.back())){ dq.push_back(box.top()); box.pop(); if(dq.size()k){ while(dq.size()){ coutdq.front(); dq.pop_front(); if(dq.size()) cout ; else coutendl; } } continue; } /* 判断推送器是不是能插 能插就插到松枝上每一次插到松枝上我都判断是不是满了 如果满了我就提前清空换松枝 */ if(posn(dq.size()0||a[pos]dq.back())){ dq.push_back(a[pos]); pos; if(dq.size()k){ while(dq.size()){ coutdq.front(); dq.pop_front(); if(dq.size()) cout ; else coutendl; } } continue; } /* 到这一步说明推送器和box都插不到松枝上 那我只能尝试将推送器上的放到box */ if(posnbox.size()m){ box.push(a[pos]); pos; continue; } /* 到这一步说明彻底没招了 那我只能清空松枝 */ while(dq.size()){ coutdq.front(); dq.pop_front(); if(dq.size()) cout ; else coutendl; } } //收尾工作将最后一个松枝上的元素给输出 while(dq.size()){ coutdq.front(); dq.pop_front(); if(dq.size()) cout ; else coutendl; } }