[cf797c]Minimal string（貪心+模擬）

題意：

給出了字符串s的內容，字符串t，u初始默認為空，允許做兩種操作：

1、把s字符串第一個字符轉移到t字符串最后

2、把t字符串最后一個字符轉移到u字符串最后

最后要求s、t字符串都為空，問u字符串字典序最小能是多少。

解題關鍵：

主要就是貪心，按字典序，每貪心完一個字母，往前回溯一次。

1、hash一下每個字母出現的次數，然后貪心選擇字典序最小的即可。

2、預處理每個位置能達到的最小的字母，然后貪心。tmp一定是一個單調不減的數組。

3、小于等于而不是等于的原因是abacd這種情況。

反思：

1、這種看似簡單的模擬題一定要搞明白，自己寫一下。類似于棧混洗。

2、string的這種類似java和python的用法

法1：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<char>s1;
int m1[300];
int cnt=0;
char s2[100020];
int main(){
    string s;
    int nn=0;
    cin>>s;
    for(int i=0;s[i];i++) m1[s[i]-'a']++;
    while(!m1[nn]&&nn<26)nn++;
    for(int i=0;s[i];i++){
        if(s1.empty()||m1[nn]){
            s1.push(s[i]);
            m1[s[i]-'a']--;
        }
        while(!s1.empty()&&s1.top()<=nn+'a'){//改成小于等于就過了 
            s2[cnt++]=s1.top(),s1.pop();
            while(!m1[nn]&&nn<26)nn++;        
        }
        while(!m1[nn]&&nn<26)nn++;
    }
    while(!s1.empty()) s2[cnt++]=s1.top(),s1.pop();
    printf("%s\n",s2);
}

法二：

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
stack<char>ss;
char tmp[100010],x;
int main(){
    string s;
    cin>>s;
    x='z'+5;
    for(int i=s.size()-1;i>=0;i--) x=min(x,s[i]),tmp[i]=x;//tmp[i]代表該位置能使結果到達最小的值 
    string ans="";
    for(int i=0;i<s.size();i++){
        while(!ss.empty()&&ss.top()<=tmp[i]) ans+=ss.top(),ss.pop();
        ss.push(s[i]);
    }
    while(!ss.empty()) ans+=ss.top(),ss.pop();
    cout<<ans<<"\n";
    return 0;
}

?