小沙の串串

小沙の串串

思路

先用单调栈进行贪心，保证前面是递增的。
但是最后还不一定是最优的，还的对结果进行调结
这个模拟就很棒

代码

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

int main() {
    int n,m;
    string s,ans,tmp;
    cin>>n>>m>>s;
    for(auto i:s) {
        while(m&&ans.size()&&ans.back()<i) {//这里确实是一个单调栈
            tmp.push_back(ans.back());
            ans.pop_back();
            m--;
        }
        ans.push_back(i);
    }//首先是贪心进行直接排序就可以了
    while(m&&ans.size()) {//前面是单调栈，但并不一定代表已经最优，还需要微调
        m--;
        tmp.push_back(ans.back());
        ans.pop_back();
    }
    sort(tmp.rbegin(),tmp.rend());
    ans+=tmp;
    cout<<ans;
    return 0;
}
//这个模拟就很简洁明了了