2019 计蒜之道 复赛 D “星云系统”

2019 计蒜之道 复赛 D “星云系统”

题目

现在给定你一个字符串s以及一个整数k，请求出s的字典序最小的长度为k的子序列。
题目链接https://nanti.jisuanke.com/t/39614

输入格式

第一行一个由小写英文字母构成的字符串s，第二行一个正整数k。

输出格式

一行一个字符串ans，表示答案。

数据规模

0<k<=|s|<=5000000

样例输入

helloworld
5

样例输出

ellld

题解

设串长为n，则只需删掉n-k个字符。
用一个单调栈维护，依次将字符串的每个字符插入，如果当前删掉的字符不足n-k个并且栈顶元素>插入的元素，那么删掉栈顶，直至删掉的字符达到n-k或者满足单调栈的性质。
最后取栈里前k个字符输出即可。
直接用字符数组模拟单调栈即可，此题的数据范围用STL会爆的！！！

代码

#include <iostream>
#include <stdlib.h>
#include <string>
#include <math.h>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include <deque>
#include <vector>

using namespace std;

int main()
{
    string s;
    Char str[5000005];//用于模拟单调栈
    int n,i;
    cin >> s;
    scanf(“%d”, &n);
    int len = s.length();
    Int flag = len - n;//统计还可以删掉多少个字符
    Int point = 0;//用于指向当前的栈顶位置
    str[0] = s[0];
    for (I=1;i<len;i++)
    {
        if (flag!=0)
        {
            While ((s[i]<str[point]&&(flag!=0)))//如果当前栈中有字符，且栈顶字符大于要插入的字符，则删掉栈顶字符
            {
                flag—;
                point—;
                if (point == -1)
                break;
            }
            point++;//找到栈中比当前要插入的字符大的字符的位置后插入字符
            str[point] = s[I];
        }
        else
        {
            point++;//如果没有可以删掉的字符了，则剩下所有的字符都依次插入
            str[point] = s[I];
        }
    } 
    for (I=0;i<n;i++)
    printf("%c", str[i]);
}

P.S. 请忽略那么多的include，仅仅是因为懒得选，所以无论做什么题目都是这一个模版直接全加上?