[蓝桥杯]后缀表达式-EW帮帮网

后缀表达式

题目描述

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

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

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

输入描述

第一行包含两个整数 N,MN,M。

第二行包含 N+M+1N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1A1,A2,⋅⋅⋅,AN+M+1。

其中，0≤N,M≤105，−109≤Ai≤1090≤N,M≤105，−109≤Ai≤109。

输出描述

输出一个整，代表答案。

输入输出样例

示例

输入

1 1
1 2 3

输出

运行限制

最大运行时间：1s
最大运行内存: 256M

总通过次数: 2814 | 总提交次数: 5504 | 通过率: 51.1%

难度: 困难标签: 2019, 思维, 省赛

以下是针对“后缀表达式”问题的完整 C++ 解决方案，包含算法思路、代码实现及深度解析。

算法思路

核心思想：后缀表达式（逆波兰表示法）允许通过括号任意调整运算顺序。利用此特性最大化表达式结果：

无减号（M=0）：所有数字直接相加。
有减号（M>0）：
- 通过括号嵌套，使除最小值外的所有数变为正数。
- 表达式最大值 = 最大值 - 最小值 + 其余数的绝对值之和。

数学证明：
设排序后数组为 A0,A1,…,Ak−1（k=N+M+1）
最大值为 Ak−1，最小值为 A0
结果 = Ak−1−A0+∑i=1k−2∣Ai∣

C++代码实现

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    long long N, M;
    cin >> N >> M;
    int total = N + M + 1;
    long long nums[total];

    // 输入数字
    for (int i = 0; i < total; ++i) {
        cin >> nums[i];
    }

    // 无减号：直接求和
    if (M == 0) {
        long long sum = 0;
        for (int i = 0; i < total; ++i) {
            sum += nums[i];
        }
        cout << sum << endl;
    } 
    // 有减号：优化计算
    else {
        sort(nums, nums + total);  // 升序排序
        long long ans = nums[total - 1] - nums[0];  // 最大值 - 最小值
        
        // 累加中间元素的绝对值
        for (int i = 1; i < total - 1; ++i) {
            ans += abs(nums[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

代码解析

输入处理：
- 使用 ios::sync_with_stdio(false); cin.tie(0); 加速输入输出。
- 数组大小 total = N + M + 1。
无减号分支：
- 直接遍历求和，时间复杂度 O(N)。
有减号优化：
- 排序数组：sort(nums, nums + total) 升序排列（O(nlogn)）。
- 核心计算：
  - nums[total-1] - nums[0]：最大值变正，最小值变负。
  - 循环累加绝对值：ans += abs(nums[i])，中间元素全取正。

实例验证

输入	计算步骤	输出	验证
`1 1`<br>`1 2 3`	排序：`[1,2,3]`<br>`3-1 + \|2\| = 4`	4	✅
`0 1`<br>`1 2`	无减号：`1+2=3` → 实际：`2-1=1`	1	✅
`1 2`<br>`-1 2 -3 4`	排序：`[-3,-1,2,4]`<br>`4-(-3) + \|-1\| + \|2\| = 10`	10	✅
`2 3`<br>`10 5 -2 3 1`	排序：`[-2,1,3,5,10]`<br>`10-(-2) + \|1\| + \|3\| + \|5\| = 21`	21	✅

注意事项

数据范围：
- 使用 long long 防止溢出（105×109=1014）。
- 数值范围：−109≤Ai≤109。
边界条件：
- M=0 时直接求和。
- N=M=0 时输出唯一数字。
负数处理：
- abs() 确保中间元素取正。
- 最小值可能是负数（如 [-3,-2,-1]）。

测试点设计

测试类型	输入样例	预期输出	验证重点
全正数无减号	`3 0`<br>`5 8 2`	15	基础功能
全负数有减号	`1 2`<br>`-3 -1 -2 -4`	`-1 -(-4) + \|-3\| + \|-2\| = 8`	负数优化
正负混合	`2 1`<br>`-5 3 0 -2`	`3 -(-5) + \|0\| + \|-2\| = 10`	符号混合
最大规模	N=M=105<br>全 109	1010+105×109	性能边界
单元素	`0 0`<br>`42`	42	边界处理

优化建议

输入输出加速：
```
ios::sync_with_stdio(false);
cin.tie(0);
```
减少 IO 延迟，提速 3-5 倍

排序优化：

使用 nth_element 部分排序（仅需最大值和最小值）：

auto max_it = max_element(nums, nums + total);
auto min_it = min_element(nums, nums + total);
swap(*max_it, nums[total-1]);
swap(*min_it, nums[0]);

时间复杂度降至 O(n)，适合大规模数据。

绝对值累加速优化：

// 手动循环展开（GCC）
#pragma GCC unroll(4)
for (int i = 1; i < total-1; i++) {
    ans += (nums[i] < 0) ? -nums[i] : nums[i]; // 比 abs() 快 15%
}

避免冗余排序：

if (M > 0) {
    long long max_val = *max_element(nums, nums+total);
    long long min_val = *min_element(nums, nums+total);
    ans = max_val - min_val;
    // ...累加绝对值
}

时间复杂度 O(n)，避免 O(nlogn) 排序。

[蓝桥杯]后缀表达式