L2-041 插松枝

人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：

每人手边有一只小盒子，初始状态为空。
每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：
（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。

（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。

（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。

现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。

输入格式：
输入在第一行中给出 3 个正整数：N（≤10^3），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。

随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。

输出格式：
每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
8 3 4
20 25 15 18 20 18 8 5
输出样例：
20 15
20 18 18 8
25 5

分析

这个题模拟的逻辑挺重要，一不小心就会漏个条件判断之类，造成死循环或者答案错误；栈stk模拟盒子，队列que模拟，动态数组v模拟一个松枝，我们在自己定义的print函数中，输出结束记得把vector进行清空数据，方便下一个松枝去用；

1. 首先，我们要先去盒子里找，如果盒子为空，我们再去推送器上找；所以我们在循环中（循环结束条件就是盒子和推送器都没有松片了），有两个if分支，分别为去盒子找，另一个去推送器找（if条件上有盒子为空的条件）；
2. 不管在这两个哪个分支上，我们首先去判断是不是空的松枝，是的话，直接插上一个，然后注意：每当松枝上的数量发生变化，我们都要去判断一下，是不是已经插满了if (v.size() == k) { print();}）；
3. 如果这个松枝上不是上面说的空的松枝，我们就要去在相应的分支上去做处理，进行当前松枝上的判断大小是否满足，如果当前在盒子的if分支上，我们就去找推送器；如果当前在推送器这个if分支上，我们去判断大小满足情况，然后如果不满足，我们就要去看盒子是否已满，如果已满就要结束这个松枝，否则放进盒子；
4. 需要记着，每当对v进行了push_back，说明v的数量发生变化，紧接着就要去判断是否插满；每当需要往盒子里放松针，都要判断盒子是否已满(stk.size() == m)；
5. 输出松枝的条件：①推送器的不符合，但盒子满了（发生在取推送器的时候不满足，对盒子进行判断后的处理）②盒子不符合，找推送器但是推送器为空了（发生在去找推送器时候，推送器已经空了）③松枝插满了v.size() == k；
6. 总而言之，先找盒子，盒子不满足找推送器，推送器不满足考虑放不放盒子里，分别做出相应处理；

#include 

using namespace std;

stack<int> stk;
queue<int> que;
vector<int> v;
int n, m, k;

void print() {
    if (v.empty())
        return;
    for (int i = 0; i < v.size(); ++i) {
        if (i != 0)
            cout << " ";
        cout << v[i];
    }
    //记着清空供下一个松枝用
    v.clear();
    cout << endl;
}

//放进盒子，要判断是否已满
//取推送器，要判断是否已空
//要判断是不是新的一个松枝
int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        int val;
        cin >> val;
        que.push(val);
    }

    while (!(que.empty() && stk.empty())) {

        //盒子空，去推送器取
        if (stk.empty() && !que.empty()) {
            if (v.size() == 0) {
                //直接插上去，不用比大小
                v.push_back(que.front());
                que.pop();
                //v的长度变化,第三种情况结束这个松枝
                if (v.size() == k)
                    print();
            } else {
                //需要比大小
                if (que.front() <= v.back()) {
                    //推送器满足条件
                    v.push_back(que.front());
                    que.pop();
                    //v的长度变化
                    if (v.size() == k) {
                        print();
                    }
                } else {
                    //推送器不满足条件,将其放进盒子
                    //盒子已满
                    if (stk.size() == m) {
                        //符合第一种情况，推送器不满足条件，但盒子已满
                        print();
                    }
                    //盒子可以放
                    if (stk.size() < m) {
                        stk.push(que.front());
                        que.pop();
                    }

                }
            }
        }

        //盒子不空,先看盒子，再去看推送器
        if (!stk.empty()) {
            if (v.size() == 0) {
                //直接插上去，不用比大小
                v.push_back(stk.top());
                stk.pop();
                //v的长度变化,第三种情况结束这个松枝
                if (v.size() == k)
                    print();
            } else {
                //比大小
                if (stk.top() <= v.back()) {
                    //盒子满足
                    v.push_back(stk.top());
                    stk.pop();
                    //v的长度变化
                    if (v.size() == k) {
                        print();
                    }
                } else {
                    //盒子不满足，去推送器取

                    if (!que.empty()) {
                        //推送器满足就取下来，否则判断放盒子里
                        if (que.front() <= v.back()) {
                            //满足
                            v.push_back(que.front());
                            que.pop();
                            //v的长度变化
                            if (v.size() == k)
                                print();
                        } else {
                            //推送器不满足条件,将其放进盒子
                            //盒子已满
                            if (stk.size() == m) {
                                //符合第一种情况，推送器不满足条件，但盒子已满
                                print();
                            }
                            //盒子可以放
                            if (stk.size() < m) {
                                stk.push(que.front());
                                que.pop();
                            }
                        }
                    } else {
                        //盒子不满足，推送器也没了，满足第二种情况
                        print();
                    }
                }
            }
        }
    }
    //最后盒子和推送器用完时，插花也要输出（因为while条件退出，没把最后一支输出）
    print();
    return 0;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129