文章目录
前言
蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十讲：贪心【习题】
本篇博客所包含习题有：
👊付账问题
👊乘积最大
👊后缀表达式
贪心【例题】见博客：蓝桥杯第十讲–贪心【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
付账问题
来源： 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组
题目要求
题目描述：
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有
n
n
n 个人出去吃饭，他们总共消费了
S
S
S 元。
其中第
i
i
i 个人带了
a
i
a_i
ai 元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为
S
S
S 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是
1
1
1 分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第
i
i
i 个人付的钱为
b
i
b_i
bi 元，那么标准差为 :
s
=
1
n
∑
i
=
1
n
(
b
i
−
1
n
∑
i
=
1
n
b
i
)
2
s=\sqrt{\frac{1}{n}\sum_{i=1}^{n}(b_i-\frac{1}{n}\sum_{i=1}^{n}b_i)^2}
s=n1∑i=1n(bi−n1∑i=1nbi)2
输入格式：
第一行包含两个整数
n
n
n、
S
S
S；
第二行包含
n
n
n 个非负整数
a
1
,
…
,
a
n
a_1, …, a_n
a1,…,an。
输出格式：
输出最小的标准差，四舍五入保留
4
4
4 位小数。
数据范围：
1
≤
n
≤
5
×
1
0
5
,
1≤n≤5×10^5,
1≤n≤5×105,
0
≤
a
i
,
S
≤
1
0
9
0≤a_i,S≤10^9
0≤ai,S≤109
输入样例1：
5 2333
666 666 666 666 666
输出样例1：
0.0000
输入样例2：
10 30
2 1 4 7 4 8 3 6 4 7
输出样例2：
0.7928
思路分析
我们对数组从小到大进行排序后遍历数组，贪心的思维是：如果你的钱数够负平均后的钱数，那么就付一个平均的钱数，否则的话，付掉你所有的钱数，然后让你后面的人均摊你不够的钱数。
代码
#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>usingnamespace std;constint N =500010;int a[N];intmain(){int n;double s;scanf("%d%lf",&n,&s);for(int i =0; i < n; i ++)scanf("%d",&a[i]);sort(a, a + n);double res =0, avg = s / n;for(int i =0; i < n; i ++){double cur = s /(n - i);if(a[i]< cur) cur = a[i];
res +=(cur - avg)*(cur - avg);
s -= cur;}printf("%.4lf\n",sqrt(res / n));return0;}
乘积最大
来源： 第九届蓝桥杯省赛C++B组
题目要求
题目描述：
给定
N
N
N 个整数
A
1
,
A
2
,
…
A
N
A_1,A_2,…A_N
A1,A2,…AN。
请你从中选出
K
K
K 个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以
1000000009
1000000009
1000000009 的余数。
注意，如果
X
<
0
X<0
X<0， 我们定义
X
X
X 除以
1000000009
1000000009
1000000009 的余数是负
(
−
X
)
(−X)
(−X)除以
1000000009
1000000009
1000000009 的余数，即：
0
−
(
(
0
−
x
)
%
1000000009
)
0−((0−x)\%1000000009)
0−((0−x)%1000000009)
输入格式：
第一行包含两个整数
N
N
N 和
K
K
K。
以下
N
N
N 行每行一个整数
A
i
A_i
Ai。
输出格式：
输出一个整数，表示答案。
数据范围：
1
≤
K
≤
N
≤
1
0
5
,
1≤K≤N≤10^5,
1≤K≤N≤105,
−
1
0
5
≤
A
i
≤
1
0
5
−10^5≤A_i≤10^5
−105≤Ai≤105
输入样例1：
5 3
-100000
-10000
2
100000
10000
输出样例1：
999100009
输入样例2：
5 3
-100000
-100000
-2
-100000
-100000
输出样例2：
-999999829
思路分析
- k == n:全选
- k是偶数个:- 负数有偶数个:两个两个选:最小的两个负数或最大的两个正数(乘积最大) res >= 0- 负数有奇数个:挑出最大的负数(永远不选),问题转变为负数有偶数个 res >= 0
- k是奇数个:- 全为负数:从最大的负数开始往小选 res < 0- 至少有一个非负数:选择这一个非负数,问题转变为k是偶数个 res >= 0
代码
#include<cstdio>#include<algorithm>#include<cstring>usingnamespace std;typedeflonglong LL;constint N =100010, MOD =1000000009;int n, k;int a[N];intmain(){scanf("%d%d",&n,&k);for(int i =0; i < n; i ++)scanf("%d",&a[i]);sort(a, a + n);int res =1;int l =0, r = n -1;int sign =1;if(k %2){
res = a[r --];
k --;if(res <0) sign =-1;}while(k){
LL x =(LL)a[l]* a[l +1], y =(LL)a[r]* a[r -1];if(x * sign > y * sign){
res = x % MOD * res % MOD;
l +=2;}else{
res = y % MOD * res % MOD;
r -=2;}
k -=2;}printf("%d\n", res);return0;}
后缀表达式
来源： 第十届蓝桥杯省赛C++B组,第十届蓝桥杯省赛JAVAB组
题目要求
题目描述：
给定
N
N
N 个加号、
M
M
M 个减号以及
N
+
M
+
1
N+M+1
N+M+1 个整数
A
1
,
A
2
,
⋅
⋅
⋅
,
A
N
+
M
+
1
A_1,A_2,⋅⋅⋅,A_{N+M+1}
A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这
N
N
N 个加号、
M
M
M 个减号以及
N
+
M
+
1
N+M+1
N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用
123
+
−
123+−
123+−，则
“
23
+
1
−
”
“23+1−”
“23+1−” 这个后缀表达式结果是
4
4
4，是最大的。
输入格式：
第一行包含两个整数
N
N
N 和
M
M
M。
第二行包含
N
+
M
+
1
N+M+1
N+M+1 个整数
A
1
,
A
2
,
⋅
⋅
⋅
,
A
N
+
M
+
1
A_1,A_2,⋅⋅⋅,A_{N+M+1}
A1,A2,⋅⋅⋅,AN+M+1。
输出格式：
输出一个整数，代表答案。
数据范围：
0
≤
N
,
M
≤
1
0
5
,
0≤N,M≤10^5,
0≤N,M≤105,
−
1
0
9
≤
A
i
≤
1
0
9
−10^9≤Ai≤10^9
−109≤Ai≤109
输入样例：
1 1
1 2 3
输出样例：
4
思路分析
本题最为关键的就是分析出，虽然有
M
M
M 个减号，但是我们最终呈现出来的其实并非必须是
M
M
M 个减号，比如我们可以把
M
−
1
M-1
M−1 个减号放入到括号中，这样就可以改变减号的个数：
a
1
−
(
a
2
−
a
3
−
a
4
)
=
a
1
−
a
2
+
a
3
+
a
4
a_1-(a_2-a_3-a_4)=a_1-a_2+a_3+a_4
a1−(a2−a3−a4)=a1−a2+a3+a4，有
N
N
N 个加号，但是我们也可以用括号去改变加号的个数：
a
1
−
(
a
2
+
a
3
+
a
4
)
=
a
1
−
a
2
−
a
3
−
a
4
a_1-(a_2+a_3+a_4)=a_1-a_2-a_3-a_4
a1−(a2+a3+a4)=a1−a2−a3−a4，你可能有疑问？本题是后缀表达式，且只有加减两种运算，怎么能出现括号呢？我们知道，每一个后缀表达式都对应一颗树，如：
a
1
−
a
2
−
a
3
−
a
4
a_1-a_2-a_3-a_4
a1−a2−a3−a4 对应下图所示树：
那么我们做简单变化其实就可以实现
a
1
−
(
a
2
−
a
3
−
a
4
)
a_1-(a_2-a_3-a_4)
a1−(a2−a3−a4)：
所以，对于
N
N
N 个加号和
M
M
M 个减号，我们其实可以构造出
1
1
1 ~
N
+
M
N+M
N+M 个减号，
1
1
1 ~
N
+
M
−
1
N+M-1
N+M−1个加号，即如果
M
>
0
M>0
M>0，则必有最少一个减号，所以我们可以对数组进行一个排序，然后用数组的最大值减去最小值，对于数组的其他元素，我们可以自由它们的加减，故对正数用加法，负数用减法，即每次让
r
e
s
res
res 加上各个元素的绝对值即可。
代码
#include<cstdio>#include<cstring>#include<algorithm>usingnamespace std;constint N =200010;typedeflonglong LL;int a[N];intmain(){int n, m;scanf("%d%d",&n,&m);for(int i =0; i < n + m +1; i ++)scanf("%d",&a[i]);sort(a, a + n + m +1);
LL res =0;if(!m)for(int i =0; i < n + m +1; i ++) res += a[i];else{
res = a[n + m]- a[0];for(int i =1; i < n + m; i ++) res +=abs(a[i]);}printf("%lld\n", res);return0;}
版权归原作者 辰chen 所有， 如有侵权，请联系我们删除。