C. Minimal string(思维+贪心+细节)-白红宇

C. Minimal string(思维+贪心+细节)

阅读量：241 次

发布时间：2019-03-01

本文共 815 字，大约阅读时间需要 2 分钟。

题意:给出一个字符串，按照从前到后的顺序进栈，输出字典序最小的出栈序列

思路：最开始贪心，预处理一个后缀，看是否存在比栈顶更小的。有就按下不放出来。然后wa17...以为贪心不行。改成一个处理每个位置的next，然后26枚举到最后能放。最后倒序一遍。依然wa17.

然后发现,栈顶之下的元素虽然比栈顶大，但是不一定比后缀大，这边要while不停的判一下栈顶。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         #include
          
           #include
           
            #include
            
             #define debug(a) cout<<#a<<"="<
             <
              
               s;int main(void){ cin.tie(0);std::ios::sync_with_stdio(false); cin>>(str+1);LL n=strlen(str+1); memset(suf,0x3f,sizeof(suf)); for(LL i=n;i>=1;i--){ suf[i]=min(suf[i+1],(LL)(str[i]-'a'+1)); } vector
               
                v; for(LL i=1;i<=n;i++){ if(s.empty()){ s.push(str[i]); } else{ while(!s.empty()){ if((s.top()-'a'+1)<=suf[i]){ v.push_back(s.top()); s.pop(); } else break; } s.push(str[i]); } } while(!s.empty()){ v.push_back(s.top());s.pop(); } for(auto i:v){ cout<

转载地址：http://eict.baihongyu.com/

你可能感兴趣的文章