9、后缀表达式

题目 后缀表达式

思路分析

概念不清楚 写不出

后缀表达式是什么

后缀表达式，是因为后缀表达式不再引用括号（其实是隐式的引用括号），比如2 3 + 1 - 这个式子，就是(2+3)−1=4, 从左向右计算，不考虑括号，运算符放在两个运算对象之后。

因为符号和数字的顺序可以随便安排，那么可以考虑下面几种情况：

如果都是加号：那么直接将所有的数字全部加起来即可 如果有一个减号，那么我们可以转化为 …+…−(….+….+…)的形式，即分为两部分，中间一个减号，因此只要出现一个减号那么就可以视为出现一个或多个减号等同的效果。 如果出现多个减号：也可以转化为…+…−(….+….−…)的形式，也就是说你希望它是减号时你可以把它放到括号外，你希望它是加号时，你可以把它放在括号里边，因为负负得正，因此，一个减号与多个减号可以视作一种情况。 总结一下就是：只要m>0, 那么减号的数量实际上就是1 到n+m的任何一个数字。

因此得到下列讨论结果：

如果全是加号，答案就是所有数字直接相加。 如果存在减号： 如果全是正数，那么至少有一个被减去，所以把最小的那个减去即可。 如果有正有负，那么所有正数匹配正号，所有负数匹配负号，因此将它们的绝对值直接相加 如果全是负数，那么除了维持一个最大的负数(因为负数越大它的绝对值越小)为负数之后外，其他的全部翻正。

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N=1e5+10;

LL a[2*N];

int n,m,k;

int main()

{

    cin>>n>>m;

    k=n+m+1;

    for(int i=1;i<=k;i++)

        cin>>a[i];

    LL sum=0;

    if(!m){

        for(int i=1;i<=k;i++)

            sum+=a[i];

        cout<<sum<<endl;

        return 0;

    }

    sort(a+1,a+k+1);

    sum+=a[k];

    sum-=a[1];

    m--;

    for(int i=2;i<k;i++)

        sum+=abs(a[i]);

    cout<<sum;

    return 0;

}

同类题型

视频讲解

⬅️ 8、等差数列 🏠 00-刷题理模型 ➡️ 第十届 c++ B组 省赛