E-Early Orders 题解

前两天打了2021年度训练联盟热身训练赛第一场

这个e题还是蛮不错的

链接：https://ac.nowcoder.com/acm/contest/12606/E

样例输入

链接：https://ac.nowcoder.com/acm/contest/12606/E
来源：牛客网

示例1
输入
6 3
3
2
1
3
1
3

输出
2 1 3

示例2
输入
10 5
5
4
3
2
1
4
1
1
5
5

输出
3 2 1 4 5

题意大概是：给出一段数字序列，要求按照顺序取元素组成子列，子列有1-k的数字，并且子列值最小

这道题可以用栈来解决：先把第一个元素压入栈，然后接下来判断栈顶元素是否大于当前元素值，是的话就弹出（前提是后面还存在这个元素，以便于它可以再次被压进来）

如果当前元素以及在栈里面，那么上述规则不生效（防止同一多次压进去）

最后，代码是这样子的：

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

#define MAXN 200005
int x[MAXN] = { 0 };
int js[MAXN] = { 0 };
bool in_stack[MAXN] = { false };

int main()
{
    int k, n;
    scanf("%d%d", &n, &k);

    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &x[i]);
        js[x[i]]++;
    }

    stack<int> s;
    s.push(x[0]);
    js[x[0]]--;
    in_stack[x[0]] = true;

    for (int i = 1; i < n; ++i)
    {
        js[x[i]]--;
        //if(x[i]==1) cout<<"aaa"<<in_stack[1]<<endl;
        while (!s.empty() && (s.top() > x[i]) && (js[s.top()] > 0) && in_stack[x[i]] == false)
        {
            in_stack[s.top()] = false;
            s.pop();
        }
        if (in_stack[x[i]] == false)
        {
            s.push(x[i]);
            in_stack[x[i]] = true;
            //cout<<x[i]<<' '<<in_stack[x[i]]<<endl;
        }

    }
    list<int> li;

    while (!s.empty())
    {
        li.push_front(s.top());
        s.pop();
    }

    while (!li.empty())
    {
        printf("%d", li.front());

        if (li.size() > 1)
            printf(" ");
        else printf("\n");


        li.pop_front();
    }
    //system("pause");
}

转载请注明来源：https://www.longjin666.top/?p=813

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~