洛谷P1750《出栈序列》

十月 06, 2018 4034

这题和栈有多少关系

题目描述

给定一个由n个元素构成的序列，你需要将其中的元素按顺序压入一个大小为c的栈并弹出。元素按它们的出栈顺序进行排列，会得到一个新的序列。我们知道，这样的序列会有很多种，请输出所有新序列中第一个元素最小的序列（若第一个元素最小的序列有多个，则令第二个尽可能小；若仍有多个，则令第三个最小，以此类推）。

Input / Output 格式 & 样例

输入格式

第一行，两个数n,c

第二行n个数，为序列中n个元素的值

输出格式

输出n个数，为满足要求的序列。

输入样例

1
2
6 3
5 2 3 8 7 4

输出样例

1
2 3 5 4 7 8

数据范围

对于40%的数据，n<=12

对于100%的数据，c<=n<=10000，元素大小均在2*10^9以内。

代码实现

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
130
131
132
133
/* -- Basic Headers -- */
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

/* -- STL Iterators -- */
#include <vector>
#include <string>
#include <stack>
#include <queue>

/* -- External Headers -- */

/* -- Defined Functions -- */
#define For(a,x,y) for (int a = x; a <= y; ++a)
#define Forw(a,x,y) for (int a = x; a < y; ++a)
#define Bak(a,y,x) for (int a = y; a >= x; --a)

/* -- Defined Words -- */

using namespace std;

namespace FastIO {
    void DEBUG(char comment[], int x) {
        cerr << comment << x << endl;
    }

    inline int getint() {
        int s = 0, x = 1;
        char ch = getchar();
        while (!isdigit(ch)) {
            if (ch == '-') x = -1;
            ch = getchar();
        }
        while (isdigit(ch)) {
            s = s * 10 + ch - '0';
            ch = getchar();
        }
        return s * x;
    }
    inline void __basic_putint(int x) {
        if (x < 0) {
            x = -x;
            putchar('-');
        }
        if (x >= 10) __basic_putint(x / 10);
        putchar(x % 10 + '0');
    }

    inline void putint(int x, char external) {
        __basic_putint(x);
        putchar(external);
    }
}

namespace Solution {
    const int MAXN = 10000 + 10;
    
    struct Stack {
        private:
            int __builtin_sequence[MAXN];
            int tail;
        
        public:
            Stack() {
                memset(__builtin_sequence, 0, sizeof(__builtin_sequence));
                tail = 0;
            }
        
            void push(int x) {
                __builtin_sequence[++tail] = x;
            }
            void pop() {
                --tail;
            }
            int top() {
                return __builtin_sequence[tail];
            }
            bool empty() {
                return tail == 0;
            }
            int size() {
                return tail;
            }
    } stk; 
    
    int n, c;
    int seq[MAXN];
}

int main(int argc, char *const argv[]) {
    #ifdef HANDWER_FILE
    freopen("testdata.in", "r", stdin);
    freopen("testdata.out", "w", stdout);
    #endif
    using namespace Solution;
    using namespace FastIO;
    n = getint();
    c = getint();
    int used = 0;
    int unusedNum = 1;
    For (i, 1, n) {
        seq[i] = getint();
    }
    while (stk.size() + used < n) {
        int inQueue = stk.size();
        int origUnusedNum = unusedNum;
        int minN = 2147482333;
        int len = c - inQueue;
        for (int i = origUnusedNum; i <= n && i < origUnusedNum + len; ++i) {
            if (seq[i] < minN) {
                unusedNum = i;
                minN = seq[i];
            }
        }
        if (stk.empty() || minN < stk.top()) {
            For (i, origUnusedNum, unusedNum) {
                stk.push(seq[i]);
            }
            ++unusedNum;
        } else unusedNum = origUnusedNum;
        putint(stk.top(), ' ');
        ++used;
        stk.pop();
    }
    while (!stk.empty()) {
        putint(stk.top(), ' ');
        stk.pop();
    }
    return 0;
}