ZOJ3829---模拟，贪心-白红宇

ZOJ3829---模拟，贪心

阅读量：4635 次

发布时间：2019-06-09

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

　　这是2014年ACM亚洲区预赛牡丹江现场赛的一道题，铜牌题，可惜当时一路WA到死。。。

只有乘法的后缀表达式的特点有两个：（1）数字的数量一定大于‘*’的数量（2）最后一位一定是‘*’；

数字比*多的话，*怎么排列都无所谓，因为1111即可以看成4个1，也可以看成1111，总可以与‘*’

结合。所以在模拟之前做以下预处理：（1）把缺少的数字补上（2）把最后一位1与前面的任何‘*’交换

开始模拟，一个‘*’能被结合，必须前面有大于或者等于2个数字，所以设置一个栈，遇到一个栈，就入

栈一个数字，遇到一个‘*’，如果栈里面1的个数少于2个，则把‘*’与后面的数字交换，等stack里的数字》=2时；

出栈一次，模拟到字符串尾即可；

至于why，只要数字够用即可，所以当遇到‘*’前面的数字不够时，不是插入1，而是将*与后面的1交换。。总之是fuck the dog！。。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define INF 0x3f3f3f3fusing namespace std;const int maxn = 10005;typedef long long ll;int t;string ss;int len;int main(){ //freopen("in","r",stdin); scanf("%d",&t); while(t--) { stack
            
              s; queue
             
               que; ss = ""; cin>>ss; len = ss.size(); int op = 0; int sch = 0,snum = 0; int pos; for(int i = 0; i < len; ++i) { if(ss[i] == '*') sch++; else snum++; } if(sch >= snum){ for(int i = 0; i < sch-snum+1; ++i) { ss='1'+ss; } op+=sch-snum+1; } if(sch > 0&&ss[ss.size() - 1] != '*'){ for(int i = 0; i < ss.size(); ++i) if(ss[i] == '*') { pos = i;break; } swap(ss[pos],ss[ss.size() - 1]); op+=1; } for(int i = ss.size() - 1; i >= 0; --i) { if(ss[i] != '*') que.push(i); } for(int i = 0; i < ss.size(); ++i) { if(ss[i] == '*') { if(s.size() == 1){ pos = que.front();//cout<
              
               <