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

· · 题解

1. 编程思路。

题目给出了后缀表达式中加号的个数为 n，减号的个数为 m。在输入数据 a_i 时进行预处理，统计出所有正数的个数（设为 p）、正数的和（设为 psum）和最小的正数（设为 pmin），同时也统计出所有负数的个数（设为 q）、所有负数的和（设为 nsum）和最大的负数（设为 nmax）。

要使后缀表达式的值最大，分以下四种情况讨论。

1）m=0，没有减号，只能将全部数加起来，因此表达式的值为 psum+nsum。

2）有减号，但全部的数均为正数，即 m\ne 0 \ and \ p=n+m+1。此时可以这样利用减号。

如果只有 1 个减号（m=1），很简单，减去最小的正数即可，答案为 psum-2\times pmin。

如果有多个减号，我们可以让最小的正数连续减去 m-1 个正数，最后用一个减号来减去这个差。形式化的表示如下：

a_1+a_2+...+a_{n+1}-(pmin-a_{n+2}-a_{n+3}-...-a_{n+m}) =a_1+a_2+...+a_{n+1}+a_{n+2}+a_{n+3}+...+a_{n+m}-pmin =psum-2\times pmin

3）有减号，但全部的数均为负数，即 m\ne 0 \ and \ q=n+m+1。此时可以这样利用减号。

如果只有 1 个减号，同样简单，用最大的负数（绝对值最小）减去其他所有负数的和，这样相当其他所有负数和的绝对值减去一个绝对值最小的负数，表达式的值肯定最大，为 -nsum+2\times nmax。

如果有多个减号，我们可以让最大的负数连续减去 m-1 个负数，最后用一个减号来减去其他 n+1 个负数的和。形式化的表示如下：

nmax-a_1-a_2-...-a_{m-1}-(a_{m}+a_{m+1}+...+a_{n+m}) =nmax-(a_1+a_2+...+a_{m-1}+a_{m}+a_{m+1}+...+a_{n+m}) =-nsum+2\times nmax

4）有减号，并且也有正数，也有负数。此时处理起来简单。用减号减去负数即可。

如果负数个数比减号多，可以采用 -(a_i+a_j) 的形式处理，其中 a_i 与 a_j 均为负数；

如果负数的个数比减号少，可以采用 -(a_i-a_j) 的形式处理，其中 a_i 是负数，a_j 是正数。

总之，最后结果一定是所有正数和负数的绝对值相加，后缀表达式的值也最大，为 psum-nsum。

2. 源程序。

#include <stdio.h>
int main()
{
    int n,m,p=0,q=0;
    scanf("%d%d",&n,&m);
    long long psum=0,nsum=0;
    long long pmin=2000000000,nmax=-2000000000;
    int i;
    for (i=0;i<n+m+1;i++)
    {
        long long num;
        scanf("%lld",&num);
        if (num>0ll)
        {
            p++;
            psum+=num;
            if (pmin>num) pmin=num;
        }
        else
        {
            q++;  nsum+=num;
            if (nmax<num) nmax=num;
        }
    }
    if (m==0)       // 负号个数为0
        printf("%lld\n",psum+nsum);
    else
    {
        if (p==n+m+1)         // 全部为正数
            printf("%lld\n",psum-2*pmin);
        else if (q==n+m+1)   // 全部为负数
            printf("%lld\n",-nsum+2*nmax);
        else
            printf("%lld\n",psum-nsum);
    }
    return 0;
}