有参加蓝桥杯的同学可以给博主点个关注，博主也在准备蓝桥杯，可以跟着博主的博客一起刷题。

文章目录

• 蓝桥杯
• 贪心（上）
• • 例题
  • • AcWing1055.股票买卖II
    • AcWing104.货仓选址
  • 第九届2018年蓝桥杯真题
  • • AcWing1235.付账问题
    • AcWing1239.乘积最大

蓝桥杯

我的AcWing

题目及图片来自蓝桥杯C++ AB组辅导课

贪心（上）

贪心 顾名思义 我们在考虑的时候很贪婪：① 找一个最优解 ② 短视（只考虑眼前的）

y总：我个人认为贪心是所有算法题里面最难的一章，比dp还要难一些，因为贪心的题没有固定的套路，可能两道贪心题没有任何的关联，它的跳跃性非常强，代码很短，但结论的证明很难，很难想出来。

那考试的时候遇到贪心题怎么办呢？一般有两种做法：

① 看一下这个贪心题是否和我们之前做过的题是相似的，然后用当时的那道题套一下看看能不能做出来。
② 只能靠猜，猜完的话可以尝试证明出来，但是很难。

例题

AcWing1055.股票买卖II

通过什么样的方式去买可以让我们获得最大收益

第一个样例，我们可以在第2天买入，第3天卖出，获利4元，然后可以从第4天买入，第5天卖出，获利3元，总获利7元。

第二个样例，我们在第1天买入，第5天卖出，总获利4元。

但我们交易不一定只有一种方案，我们可以在第1天买入，第3天卖出，获利2元，第3天买入，第5天卖出，获利2元，总获利4元。

也就是说不一定只有一种方案可以取得最大值。

第三个样例，比较极端的一种情况，没有获利，因为股票处于垂式，不断递减，所以此时的收益为0。

贪婪的策略：依次看相邻的两天，只要后 > 前，则交易一次，这样最终得到的一定是最优值。

有一个性质，我们可以从第二个样例发现：任何一个跨度超过一天的交易一定等价于若干个跨度等于一天的交易拼起来。

对于我们这个问题的任何买卖方式，我们都一定可以把它拆分成全部跨度都为1天的交易，所以我们只需要关注相邻的两个天数，如果收益为正，则一定要操作。

核心：把所有交易拆分成跨度为1的交易

证明：对于任何一个交易都一定等价于一堆跨度为1的交易的集合

只要证明成功，代码就非常简单了：

import java.util.Scanner;public class Main { static final int N = 100010;    static int[] a = new int[N];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for (int i = 0; i < n; i++) a[i] = sc.nextInt(); int res = 0; for (int i = 0; i < n; i++) {     if (a[i + 1] > a[i]) {  res += a[i + 1] - a[i];     } } System.out.print(res);    }}

AcWing104.货仓选址

这道题似曾相识，在小学的时候就做过这种题，建一个仓库，使得仓库到每家商店距离之和最小：

看样例，也就是建在2的位置：

简单猜想一下：如果有奇数个商店，我们应该把仓库建到中位数的位置；如果有偶数个商店，应该建在中间两个商店之间。

那我们怎么证明呢？我们可以用公式来推导，先把问题转换成数学模型：

假设最终仓库的位置是C，我们需要求|A1 - C| + |A2 - C| + ... + |An - C|的最小值。

我们可以采用分组的思想，把不同的项分一组，第一项和最后一项一组，第二项和倒数第二项一组，公式先假设这个数列有奇数个，奇偶数的最后一组是不同情况的，奇数最后一组只有一项，偶数最后一组有两项：

看一下每一组的最小值，假设第一项是|Ai - C|，第二项是|Aj - C|，如果C在Ai和Aj之间，那么距离之和为Aj - Ai，如果C在Ai左边，那么就是Aj - Ai + 2(Ai - C)，长度会更大一些，不是最小值，同理当C在Aj右边也不是最小值。

所以只要C在Ai和Aj中间那么就可以让每一项都取到最小值，此时整个等式就是最小值。

证明比较繁琐，但是代码实现还是很简单的，我们先把数组读进来然后排序，排完序让仓库取在中点，然后遍历一下每一个商店，求一下与仓库的距离，累加起来就可以了。

import java.util.Scanner;import java.util.Arrays;public class Main {    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] x = new int[n]; for (int i = 0; i < n; i++) x[i] = sc.nextInt(); Arrays.sort(x);  int c = x[n / 2]; // 使仓库建在中点 int res = 0; for (int i = 0; i < n; i++) res += Math.abs(x[i] - c);  System.out.print(res);    }}

第九届2018年蓝桥杯真题

AcWing1235.付账问题

JavaA组第10题

n个人，消费S元，取平均数是 S n \frac{S}{n} nS​，① 假设所有 a i ⩾ S n a_{i}\geqslant\frac{S}{n} ai​⩾nS​，那么取 b i = S n b_{i}=\frac{S}{n} bi​=nS​，② 假设如果有 a i < S n a_{i}<\frac{S}{n} ai​<nS​，那么取 b i = a i b_{i} = a_{i} bi​=ai​，你掏不出来平均数那么多那你就有多少掏多少；他少掏的钱为 S n − a i \frac{S}{n} - a_{i} nS​−ai​，把这部分钱分摊给钱数更多的同学。

那么怎么证明我们的猜想呢？这里需要用到均值不等式思想：

先将我们的标准差表示出来：

列出均值不等式：

我们可以把标准差中分子平方内的每一项看成是 X i X_{i} Xi​，那么就由上面的公式化为下面的公式了，因为 $b1+b2+...+bn$ 的和是 $S$，n个 S n \frac{S}{n} nS​相加的和也是 $S$，所以每一项 X i X_{i} Xi​都是两数相减，分子和为 $0$，因此 x 1 2 + x 2 2 +...+ x n 2 n x_{1}^2+x_{2}^2+...+x_{n}^2 \over n nx12​+x22​+...+xn2​​ $\ge 0$，最小值也就是 $0$，且所有数相同时取到最小值，所以我们要尽可能让每一项 b i b_{i} bi​ 都相同才可以使等式达到最小值，这也印证了我们上面的猜想①。

我们还要证明我们的猜想②：

当 a i < S n a_{i}<\frac{S}{n} ai​<nS​，假如 b i b_{i} bi​ 不取 a i a_{i} ai​，而是取一个小于 a i a_{i} ai​ 的数 b i ′ b_{i}' bi′​ ，那还能是最小值了吗？当有一个数少了一点，那必然意味着某些数多了一点，那么我们任取一个大于平均数的数： b j > S n b_{j} >\frac{S}{n} bj​>nS​

我们来看一下只有两个数的均值不等式：

$a²+b²$，$a+b$是定值，看一下什么情况比较小，什么情况比较大，可以将式子变为：$2(a²+b²)-(a+b)²$，这样也并不会影响我们取最小值，整理一下变为$(a-b)$，所以当两个数的和固定时，这两个数的差越小，式子就越小，也就意味着两个数的平方和越小， b i ′ b_{i}' bi′​ 有上升空间，因此可以让 b i ′ b_{i}' bi′​ 稍微增加一部分，让 b j b_{j} bj​ 稍微减少一部分，那么整个和会变得更小，所以一定要让 b i b_{i} bi​ 取到上限也就是 a i a_{i} ai​，这样我们也证明了猜想②。

所以我们可以将所有人的钱数排序，如果第一项小于平均值，那么他有多少出多少，让后面大于平均数的人补；第二项、第三项同理，直到所有人的钱数大于等于平均数。

import java.util.Scanner;import java.util.Arrays;public class Main { static final int N = 500010;    static int[] a = new int[N]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); double s = sc.nextDouble(); for (int i = 0; i < n; i++) a[i] = sc.nextInt();  Arrays.sort(a, 0, 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 += Math.pow((cur - avg), 2) / n; // 方差     s -= cur; // 减去当前的钱数 }  System.out.printf("%.4f", Math.sqrt(res)); // 标准差    }}

代码在AcWingAC了，但是我发现在蓝桥杯评测中满分100分只拿到了70分，最后面三个数据出错了，是因为精度的问题，在课上y总的代码是double，后来更新成了long double解决了这个问题，C++换成高精度浮点数很简单，但java就没那么简单了，需要用到BigDecimal类，然后加减乘除的运算超级麻烦，我也试了一下，但可能是因为方法执行顺序的问题导致一个样例也过不了，所以就放弃了，估计是出题人故意卡这道题的分数，毕竟是最后一题，让咱们没法轻易拿到满分，但是70分也够了，如果有大佬解决了的话希望可以指点一下。

AcWing1239.乘积最大

C++B组第10题

贪心+双指针

我们先将所有正数和负数按照大小顺序排序，我们需要考虑各种情况做出判断：

① 当 $k==n$ 时，我们需要选择所有数进行相乘

② 当 $k<n$ 时，

1. k是偶数，结果必然是非负的
   (1) 负数个数为偶数个，负负得正，结果一定非负
   (2) 负数个数为奇数个，我们可以拿出来一个负数不选它，那么结果一定非负
2. k是奇数
   (1) 如果所有数都是负数，那么结果为负
   (2) 至少存在一个非负数，那么我们将最大的非负数取出来并选它，此时k的个数为偶数个，就是上面的(2)了，结果一定非负

如果k是奇数，那么我们就把最大的数选掉，如果都为负数那么选择乘积较小的组合，如果k是偶数，我们从左右两边往中间取，哪边乘积大就选哪边即可。

import java.util.Scanner;import java.util.Arrays;public class Main {    static final int N = 100010, mod = 1000000009;    static int[] a = new int[N];    public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); for (int i = 0; i < n; i++) a[i] = sc.nextInt(); Arrays.sort(a, 0, n); long res = 1; // 初始化乘积 int l = 0, r = n - 1; // 初始化双指针 int sign = 1; // 定义符号 if (k % 2 == 1) {     res = a[r--];     k--;     if (res < 0) sign = -1; // 都是负数则进行特判 将符号置为- } while (k > 0) {     long x = (long)a[l] * a[l + 1], y = (long)a[r - 1] * a[r]; // 两边成对取     if (x * sign > y * sign) { // 判断是取左边的还是右边的  res = x % mod * res % mod;  l += 2;     } else {  res = y % mod * res % mod;  r -= 2;     }     k -= 2; }  System.out.print(res);    }}

有对代码不理解的地方可以在下方评论