蓝桥杯2019年真题:后缀表达式

题目

时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分 【问题描述】 给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1,A2,··· ,AN+M+1， 小明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数 凑出的合法的后缀表达式中，结果最大的是哪一个？ 请你输出这个最大的结果。 例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。 【输入格式】 第一行包含两个整数 N 和 M。 第二行包含 N + M + 1 个整数 A1,A2,··· ,AN+M+1。 【输出格式】 输出一个整数，代表答案。 【样例输入】 1 1 1 2 3 【样例输出】 4 【评测用例规模与约定】 对于所有评测用例，0≤ N,M ≤100000，−109 ≤ Ai ≤109。

答案

这道题的第一个坑,可能你们不知道后缀表达式的定义是什么. 后缀表达式是运算符位于操作数之后,计算机从左到右扫描表达式, 遇到数字就直接入栈,遇到运算符就弹出栈顶两个数进行计算, 将结果压入数栈,一直重复得到结果

具体的可以看这篇文章

知道通过了第一个坑还有可能进入第二个坑,你有可能在想,将这些数字按照从小到大 进行排序,然后用所有的加号将大的数值加起来,然后将所有小的数值减了, 因为你觉得这道题没有括号和优先级之类的 但是这样又错了 后缀表达式是本来没有括号但是又有优先级的表达式,比如: +,+,-,-,1,2,3,4,5 如果是5+4+3-2-1=9 如果是后缀表达式5 4 3 + + 1 2 - - =13 对应中缀表达式5+4+3-(1-2)=13 所以这道题加上了后缀表达式就是有优先级的了 现在就是这道题所有的数中有正有负 如果所有都是正数,我们可以使用一个减号将其他的减号变成加号,有多少个减号 就将多少个减号放在括号里面让它变成加号,所以结果就是: 除了最小的数,所有的数加起来减去最小的数,就是 A+(B+C)-D 如果都是负数,就用加号的全部放在括号中让他变成正数,所以结果就是: 除了最大的数,其他的都是可以变成正数,可以改成 A+(B+C)-D 如果有正有负有,也是将负的全部变成正数,减号不够就用括号括起来再减 所以还是全部的绝对值加起来减去一个绝对值最小的 A+(B+C)-D 上面的(B+C)就是无论正负都可以变成正数的数, 上面所有的分类都是所有的数加起来,然后减去最小的,因为想将负数变成正数,必须 用减号来将它改成正数,但是最开始那个被减数就不能弄成正的 package competition3; import java.util.Scanner; public class ExpressionOfMy { public static int N,M; public static int[] number; public static void main(String[] args) { Scanner in = new Scanner(System.in); N=in.nextInt(); M=in.nextInt(); number=new int[N+M+1]; int min=0,max=0; for(int x=0;x<number.length;x++) { number[x]=in.nextInt(); if(number[min]>number[x]) { min=x; } if(number[max]<number[x]) { max=x; } } long sum=0; if(M==0) { for(int x=0;x<number.length;x++) { sum +=number[x]; } System.out.println(sum); } else { for(int x=0;x<number.length;x++) { sum +=Math.abs(number[x]); } sum=(sum-Math.abs(number[max])-Math.abs(number[min]))+(number[max]-number[min]); System.out.println(sum); } in.close(); } }