前言

蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事

✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十讲：贪心【例题】

本篇博客所包含习题有：

👊股票买卖 II

👊货仓选址

👊糖果传递

👊雷达设备

贪心【习题】见博客：蓝桥杯第十讲–贪心【习题】

博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！

股票买卖 II

题目要求

题目描述：

给定一个长度为 N的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式：

第一行包含整数 N ，表示数组长度。

第二行包含 N  个不大于 10000  的正整数，表示完整的数组。

输出格式：

输出一个整数，表示最大利润。

数据范围：

.

1≤N≤105

输入样例1：

6

7 1 5 3 6 4

输出样例1：

7

输入样例2：

5

1 2 3 4 5

输出样例2：

4

输入样例3：

5

7 6 4 3 1

输出样例3：

0

样例解释：

思路分析

贪心思维：两天两天去看，如果明天的价格比今天的高，那么我就在今天买入，在明天卖出。

思维证明：任何一个跨很多天的交易都可以被拆分成很多两天两天的交易。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    int res = 0;
    for (int i = 1; i < n; i ++ ) 
        if (a[i + 1] > a[i])
            res += a[i + 1] - a[i];
    printf("%d\n", res);
    return 0;
}

货仓选址

题目要求

题目描述：

在一条数轴上有 N 家商店，它们的坐标分别为 A ₁   ∼ A _N 。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式：

第一行输入整数 N 。

第二行 N  个整数A ₁   ∼ A _N。

输出格式：

输出一个整数，表示距离之和的最小值。

数据范围：

1≤N≤100000,

0≤Ai≤40000

输入样例：

4

6 2 9 1

输出样例：

12

思路分析

贪心思路：如果是奇数个商店，那么就让货仓设在最中间的那个商店上，如果是偶数个商店，那么货仓可以设置在最中间的两个商店之间的任意位置。

因为偶数个商店的最优法为最中间两个商店之间的任何位置均可，不如就设为最中间的两个商店的左商店为货仓，如此可以统一代码。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
    sort(a, a + n);
    int res = 0;
    for (int i = 0; i < n; i ++ ) 
        res += abs(a[i] - a[n / 2]);
    printf("%d\n", res);
    return 0;
}