问题

lanqiao2

思路

后缀表达式

从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

中缀表达式的括号优先级体现在后缀表达式中的字符顺序上(隐括号)，如中缀表达式（3+（5*（3+4）））对应的后缀表达式为3534+*+，求后缀表达式的最大值可以通过中缀表达式来求，更容易理解。

分情况

（1）: 当M等于0时（没有‘ - ’号），最大值即为所有数之和。

（2）: 当M大于0，因为给定数有正有负，所以需要尽可能让负数变为正数，可以利用中缀表达式中的括号... - [...]将负数置于括号内，有可能所有数都是正数只是有-运算符而已，所以需要用两个数保证表达式成立，最小损失—

max...-[min...]，剩下的算符与数值任意组合，结果为正数的放在max后面，为负的放在min后面，最终式子的结果即为最大值。

所以求最终答案的式子可以表示为 ：MAX- MIN + |a2|+ … + |an-1|

例：

N: 1 M: 2 num[]: 2 -3 4 -5

最大值： 4 + 2 - （-3） - [-5 ]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class 后缀表达式_B组_第十届 {
    static int N, M;
    static long[] num;

    public static void main(String[] args) throws IOException {
        BufferedReader read =  new BufferedReader(new InputStreamReader(System.in));
        int[] tep = Arrays.stream(read.readLine().split(" "))
                          .mapToInt(Integer::parseInt)
                          .toArray();
        N = tep[0]; M = tep[1];
        num = Arrays.stream(read.readLine().split(" "))
                    .mapToLong(Long::parseLong)
                    .toArray();

        if (M == 0){
            System.out.println(Arrays.stream(num).sum());
        }else {
            Arrays.sort(num);
            long rel = num[num.length - 1] - num[0];
            System.out.println(
                    rel + Arrays.stream(num, 1, num.length - 1)
                                .map(Math::abs)
                                .sum()
            );
        }
    }
}

小结

今天做另一道真题题：灵能传输 的时候题干提示输入量很大请用快速的读入方式，果断使用缓冲流然后想到stream以前看过想试试看，结果异常好用，这不比遍历字符串数组转换快吗？之前看了那么久的stream流那么多优点而且还是jdk1.8支持的为啥不在比赛中用呢？