P8683 [蓝桥杯 2019 省 B] 后缀表达式

题目描述

给定 NN 个加号、 MM 个减号以及 N+M+1N+M+1 个整数 A_1,A_2,\cdots,A_{N+M+1}A1​,A2​,⋯,AN+M+1​，小明想知道在所有由这 NN 个加号、 MM 个减号以及 N+M+1N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个。

请你输出这个最大的结果。

例如使用 1 2 3 + -，则 2 3 + 1 - 这个后缀表达式结果是 44，是最大的。

输入格式

第一行包含两个整数 NN 和 MM。

第二行包含 N+M+1N+M+1 个整数 A_1,A_2,\cdots,A_{N+M+1}A1​,A2​,⋯,AN+M+1​。

输出格式

输出一个整数，代表答案。

*后缀

2 3 + 1 -  ——> 5 1 - ——> 5-1=4

思路

分两种情况：

当负号=0时最大数值为N+M+1个数之和；

当负号不为0时：

1.当最小值>0时，N+M+1个数的绝对值相加-2*最小值；

2.当最大值<0时，N+M+1个数的绝对值相加+2*最大值；

 1 #include<stdio.h>
 2 int main()
 3 {
 4     int m,n,i,min=0,max=0;
 5     int a[300000];
 6     long sum=0;
 7     scanf("%d %d\n",&n,&m);
 8     for(i=0;i<n+m+1;i++)
 9     {
10         scanf("%d",&a[i]);
11     }
12     if(m!=0)
13 {
14     min=a[0];
15     max=a[0];
16     for(i=0;i<m+n+1;i++)
17     {
18         if(a[i]<min)
19         min=a[i];
20         if(a[i]>max)
21         max=a[i];
22         if(a[i]<0)
23         {
24             a[i]=-a[i];
25         }
26     }
27 }
28     
29     for(i=0;i<n+m+1;i++)
30     {
31         sum+=a[i];
32     }
33     if(min>0)
34     sum-=2*min;
35     if(max<0)
36     sum+=2*max;
37     printf("%ld",sum);
38 }