蓝桥杯每日一题2023.10.21

小鱼儿 2024-03-27 19:06 9阅读 0赞

[后缀表达式 - 蓝桥云课 (lanqiao.cn)][- _ _lanqiao.cn]

### 题目描述 ###

![2b159b5e4a924d519825cdc894dca46d.png][]

### 题目分析 ###

30分解法：要求出最大的结果就需要加的数越大，减的数越小，以此为思路简单列举即可

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 2e5 + 10;
    ll n, m, a[N], ans;
    int main()
    {
    	cin >> n >> m;
    	int len = n + m + 1;
    	for(int i = 1; i <= len; i ++)
    	{
    		cin >> a[i];
    	}
    	sort(a + 1, a + 1 + n);
    	for(int i = len; i >= 1; i --)
    	{
    		if(n >= 0)
    		{
    			ans += a[i];
    			n --;
    		}
    		else
    		{
    			ans -= a[i];
    		}
    	}
    	cout << ans;
    	return 0;
    }

但我们仔细观察会发现实际上减去的数字可以为负数，所以两个减号即可以变为正数，要将情况完全考虑出来需要讨论

满分解法：

n个加号与m个减号可以构成1到n + m个减号（所以此处需要特判如果没有减号就直接将所有数相加即可），所以至少会减一个数（1减号），至少会加一个数（n + m减号），为了使结果最大我们减去最小的数，加上最大的数，中间部分实则可以全部变为正数

#include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 10;
    int n, m, a[N], sum;
    int main()
    {
    	cin >> n >> m;
    	for(int i = 1; i <= n + m + 1; i ++)cin >> a[i];
    	if(!m)
    	{
    		for(int i = 1; i <= n + m + 1; i ++)
    		{
    			sum += a[i];
    		}	
    	}
    	else
    	{
    		sort(a + 1, a + 1 + n + m + 1);
    		sum += a[n + 1 + m];
    		sum -= a[1];
    		for(int i = 2; i <= n + m; i ++)
    		{
    			sum += abs(a[i]);
    		}
    	}
    	cout << sum;
    	return  0;
    }

[- _ _lanqiao.cn]: https://www.lanqiao.cn/problems/193/learning/?first_category_id=1&page=1&sort=students_count&second_category_id=3&name=%E5%90%8E%E7%BC%80%E8%A1%A8%E8%BE%BE%E5%BC%8F
[2b159b5e4a924d519825cdc894dca46d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/4aea79617753477b922e325179d2f1b8.png