Java教程

蓝桥杯[第十届][B组]-后缀表达式

本文主要是介绍蓝桥杯[第十届][B组]-后缀表达式,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

 

 

思路:

1.没有负号

  直接求和 

2.有负号

若干正数-若干负数+(至少有个值,选最大值)-(若干负数- 若干正数+(至少有个值,选最小值))

(后面的负数是转化为正,前面的正数是保持不变。但是前面的 -负数 和后面的 -正数其实是用来用掉多余的负号的)

如果只有一个负号,可以把正数放前面,负数放后面,如果有多个,可以 -负数放前面 或者-正数放在后面
效果是理想情况下可以把所有负号都变成正号然后求和


但如果有极端情况,比如都是负号,不过不管怎么样 最大值一定是放在前面是最优的
比如-1 -5 -9 -8 -7,负一在前面,结果为-1 - (-5-9-8-7)=28正确
如果都是正数,那么-号后面至少有一项,那么为了使和最大,必然选最小值

这样总结下来
(max+ (若干组合正数)) - (min +(若干组合负数)) =(max-min)-Sum(abs(other)) 即最大值-最小值 加上 剩下数的绝对值(处理过后都是正数)

如果min为正,那么不可能有负数出现在前后,组合负数比如 -正数可以用来用掉剩余的负号,max为负时也同理。

#include<bits/stdc++.h>
#include<cstdlib>
using namespace std;
int n,m;
int num[200005]= {0};
int cmp(const void* a,const void* b) {
    return *(int*)b-*(int*)a;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>m>>n;
    for(int i=0; i<m+n+1; i++) {
        cin>>num[i];
    }
    qsort(num,m+n+1,sizeof(int),cmp);
    long long ans=0;
    if(n==0) {
        for(int i=0; i<m+n+1; i++) {
            ans+=num[i];
        }
        cout<<ans;
        return 0;
    }
    for(int i=1; i<m+n; i++) {
        ans+=abs(num[i]);
    }
    cout<<ans+(num[0]-num[m+n]);
    return 0;
}

 

这篇关于蓝桥杯[第十届][B组]-后缀表达式的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!