前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十讲：贪心【习题】
本篇博客所包含习题有：
👊付账问题
👊乘积最大
👊后缀表达式
贪心【例题】见博客：蓝桥杯第十讲–贪心【例题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
付账问题
来源： 第九届蓝桥杯省赛C++A组,第九届蓝桥杯省赛JAVAA组
题目要求
题目描述：
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有 n 个人出去吃饭，他们总共消费了 S 元。
其中第 i 个人带了 a i 元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第 i 个人付的钱为 bi元，那么标准差为 :
输入格式：
第一行包含两个整数 n、S ；
第二行包含 n 个非负整数 a 1 , … , a n。
输出格式：
输出最小的标准差，四舍五入保留 4 位小数。
数据范围：
1≤n≤5×105,
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> using namespace std; const int N = 500010; int a[N]; int main() { 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)); return 0; }
乘积最大
来源： 第九届蓝桥杯省赛C++B组
题目要求
题目描述：
输入格式：
第一行包含两个整数 N和 K 。
以下 N 行每行一个整数 A i 。
输出格式：
输出一个整数，表示答案。
数据范围：
1≤K≤N≤105,
−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> using namespace std; typedef long long LL; const int N = 100010, MOD = 1000000009; int n, k; int a[N]; int main() { 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); return 0; }
后缀表达式
来源： 第十届蓝桥杯省赛C++B组,第十届蓝桥杯省赛JAVAB组
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数，代表答案。
数据范围：
0≤N,M≤105,
−109≤Ai≤109
输入样例：
1 1
1 2 3
输出样例：
4
思路分析
那么我们做简单变化其实就可以实现a1−(a2−a3−a4)：
代码
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 200010; typedef long long LL; int a[N]; int main() { 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); return 0; }
