天梯赛_L2-041 插松枝(stl, 模拟)

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
const int N = 1010;
int ts[N];
stack<int> hz;

vector<int> ss[N];
int cnt = 1;    // 松枝的个数，1 ~ cnt

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++) cin >> ts[i];

    int pt = 1;    // 推送器的当前松针
    while(pt <= n || !hz.empty()){    // 推送器有松针或者盒子不空
        int s = (int)ss[cnt].size();
        if(s >= k){
            cnt ++;
            continue;
        }
        if(s == 0){    // 当前是空松枝
            if(!hz.empty()){    // 盒子有松针
                int t = hz.top();
                hz.pop();
                ss[cnt].push_back(t);
            }
            else{    // 盒子没有松针，从推送器取一个松针
                int t = ts[pt ++];
                ss[cnt].push_back(t);
            }
        }
        else{    // 当前松枝非空
            int curr = ss[cnt][s - 1];
            int t;
            bool flag = false;    // 能否从盒子中取出一个松针插
            
            if(!hz.empty()){    // 盒子有松针
                t = hz.top();
                if(t <= curr){    // 盒子的松针可以插
                    hz.pop();
                    ss[cnt].push_back(t);
                    flag = true;
                }
                else if(pt > n){    // 盒子的松针不能插，而且推送器空
                    cnt ++;
                    continue;
                }
            }
            
            if(!flag){    // 不能从盒子中取松针，试从推送器取
                while(1){
                    if(pt > n){    // 推送器为空
                        cnt ++;
                        break;
                    }
                    t = ts[pt];    // 从推送器上取一个松针
                    if(t <= curr){    // 推送器的可以插
                        ss[cnt].push_back(t);
                        pt ++;
                        break;
                    }
                    else if((int)hz.size() <= m - 1){    // 推送器的不能插，但是盒子能放入松枝
                        hz.push(t);
                        pt ++;
                    }
                    else{    // 推送器的不能插，而且盒子满了
                        cnt ++;
                        break;
                    }
                }
            }
            
        }
    }

    for(int i = 1; i <= cnt; i ++){
        for(int j = 0; j <= (int)ss[i].size() - 1; j ++) cout << ss[i][j] << " \n"[j == (int)ss[i].size() - 1];
    }
    
    return 0;
}