单调栈--删除一串数字的k个数使最后结果最小

爱被打了一巴掌 2022-02-02 18:19 156阅读 0赞

题目：[http://betterang.club/problem.php?id=1205][http_betterang.club_problem.php_id_1205]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70][]

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    ll t,k,p=1,len;
    void slove(){
        stack<char> m,n;//单调栈 
        string c;
        vector<int> s;//为什么用vector? 因为数太多-_- 
        cin>>c;
        cin>>k;
        len=c.length();
        for(ll i=0;i<len;i++){
            if(m.empty()) 
    		   m.push(c[i]);
            else{
            	while(!m.empty() && m.top()>c[i] && len-k-m.size()<len-i ){//栈顶元素比当前数大且保证剩下的数足够就pop 
        	    	m.pop();
    		    }
    		    m.push(c[i]);
    		}
           
    	}
    	while(m.size()>len-k) m.pop();//保证栈中有len-k个元素 
    	while(!m.empty()){//由于栈元素的先进后出 所以要把栈中元素倒置才能将所求结果存在数组s中 
    		//cout<<m.top();
    	  n.push(m.top());
    	  m.pop();	
    	}
    	ll flag=1;
    	while(!n.empty()){
    		if(n.top()=='0' && flag==1) {//如果结果最前面是0就不用存了呀 
    			n.pop();
    		}
    		else{
    			flag=0;
    			s.push_back(n.top()-'0');
    			n.pop();
    		}
    	}
    	if(flag==1) //如果结果中只有0 
    	   cout<<0<<endl<<233<<endl;
    	else{
    		ll p=s.size();
    		for(ll i=0;i<p;i++) cout<<s[i];
    		cout<<endl;
    		if(p>3){
    		s[p-1]+=3;
    		s[p-2]+=3;
    		s[p-3]+=2;
    	    
    		for(ll i=p-1;i>0;i--){
    			if(s[i]>9) {
    				s[i-1]+=s[i]/10;s[i]%=10;
    			}
    		}
    		if(s[0]>9) {//考虑最高位进位 
    			cout<<s[0]/10;
    			s[0]%=10;
    		}
    		for(ll i=0;i<p;i++){
    			cout<<s[i];
    		}
    		
    	  }
    	  else{
    	  	ll sum=0;
    	  	for(ll i=0;i<p;i++){
    	  		sum=sum*10+s[i];
    		  }
    		  cout<<sum+233<<endl;
    	  }
       }
    }
    int main(){
    		slove();
       return 0;
    } 
    
    /*
    1023004  3
    4
    237
    
    1003 2
    0 
    233
    
    145759411 1
    14559411
    14559644
    
    99999 1
    9999
    10232 
     
    */

[http_betterang.club_problem.php_id_1205]: http://betterang.club/problem.php?id=1205
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNzIyMjE3_size_16_color_FFFFFF_t_70]: /images/20220202/0921fcd41b6c4825af140a4cda3cfbdd.png