2019年第十届蓝桥杯C/C++省赛B组试题I：后缀表达式

向右看齐 2022-10-19 14:57 117阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70][]

例子：

输入

1 1
    1 2 3

输出

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70 1][]

**贪心算法**

#include<stdio.h>
    #include<math.h>
    int n,m,a,b,i;
    int z[200005];
    int f[200005];
    long ans=0;
    //m==0
    void solve1()
    {
         for(i=1;i<=a;i++)
              ans+=z[i];
         for(i=1;i<=b;i++)
              ans+=f[i];
    }
    
    //m!=0 && m<=b && a!=0 || m!=0 && m>b && b!=0
    void solve2()
    {
         for(i=1;i<=a;i++)
              ans+=z[i];     
         for(i=1;i<=b;i++)
              ans-=f[i];
    }
    
    //m!=0 && m>b && b==0 || m!=0 && m<=b && a==0
    void solve3()
    {
    	 int maxs=-1000000000;
    	 int mins=1000000000;
         if(a==0)
    	 {     
              for(i=1;i<=b;i++)
    		  {
                   ans-=f[i];
                   if(maxs<f[i])maxs=f[i];
              }
              ans=ans+maxs*2;
         }
         else
    	 {      
              for(i=1;i<=a;i++){
                   ans+=z[i];
                  if(mins>z[i])mins=z[i];
              }
              ans=ans-2*mins;
         }
    }
    int main()
    {
    	 int i=1;
         int len;
         int sh;
         a=0,b=0;
    	 scanf("%d%d",&n,&m);
    	 len=n+m+1;
         for(i=1;i<=len;i++)
    	 {
              scanf("%d",&sh);
              if(sh<0)
                   f[++b]=sh;//负数
    		  else z[++a]=sh;//正数         
         }
         if(m==0)
    	 {
              solve1();
         }
         else{
              if((m<=b && a!=0) || (m>b && b!=0)){
                   solve2();
              }
              if( (m>b && b==0) || ( m<=b && a==0)){
                   solve3();
              }
         }
         printf("%d",ans);
    	 return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70]: /images/20221004/009c4581a97b49339e955741ea4a162a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU4MTM4NzM0_size_16_color_FFFFFF_t_70 1]: /images/20221004/9d6632e20f1b40d6bd92af0b4b58bd4a.png