C++贪心算法的使用（附带实例）

贪心算法（Greedy Algorithm）是一种在每一步选择中都采取当前状态下最好或最优的选择，从而希望最终得到一个全局最好或最优的解。简单来说，贪心算法不从整体最优考虑，它所做出的选择只是某种意义上的局部最优。

贪心算法适用于具有“最优子结构”的问题，即一个问题的最优解包含其子问题的最优解，这也是贪心算法正确的关键。也就是说，整体的最优解可以通过在每一步都选择局部最优解来逐层构建。

一般来说，贪心算法的正确性证明起来较为复杂，但我们可以通过经验总结一些常见的贪心模型，从而快速判断贪心法是否适用于某道题目。

贪心算法主要靠刷题积累，见得多了，就能产生“贪心”的直觉。

在竞赛中，如果对某道题目的贪心算法解法的正确性没有把握，可以编写一个更基础的暴力解法作为对比。通过在小范围内生成随机数据并对比两种方法的输出结果进行大量测试，如果两种方法的结果始终一致，那么可以认为贪心算法大概率是正确的。

接下来通过几道例题帮助读者理解贪心算法。

【实例 1】 StarryCoding P24最大子段和。给定一个长度为 n 的数组 a，求最大连续子段和（子段长度至少为 1）。
输入格式：

第一行包含一个整数 n，表示数组的长度（1 ≤ n ≤ 1×10^6）。
接下来一行包含 n 个整数，表示数组 a（-10^9 ≤ ai ≤ 10^9）。

输出格式：

一个整数，表示最大连续子段和。

样例输入：

5
1 2 -4 4 5

样例输出：

9

最大子段和为 a4+a5=9。

样例输入：

6
-1 -2 -3 -5 -2 -3

样例输出：

-1

解题思路：

变量 sum 表示以当前位置为右端点的最大子段和。
变量 ans 表示当前遇到的所有 sum 中的最大值，即题目要求的答案。
当我们遇到一个数字 ai，有两种情况：
- 如果 sum+ai<0，说明此时将 ai 接到之前的一个最大子段后面会导致子段和变为负数，那么还不如不接收，直接令 sum=0，从 ai+1 开始重新计算字段和。
- 如果 sum+ai≥0，说明将 ai 接到之前的最大子段后面依然可以为之后的行为作出贡献，就将 ai 留下，更新 sum+=ai 和 ans=max(ans, sum)。

但是，这里需要注意 ans 的初始值应设置为 a1 而不是 0，因为子段长度必须大于 0，可能存在全为负数的情况。

实现代码如下：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;         // 定义长整型别名 ll
const int N = 1e6 + 9;        // 定义常量 N，表示数组的最大长度
ll a[N];                      // 定义一个长整型数组 a，用于存储输入的数据

int main() {                  // 主函数
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);  // 优化输入/输出流性能
    int n; cin >> n;          // 输入整数 n，表示数组的长度
    for (int i = 1; i <= n; ++i) cin >> a[i];  // 输入数组 a 的元素
    ll sum = 0, ans = a[1];   // 初始化 sum 为 0，ans 为数组第一个元素
    for (int i = 1; i <= n; ++i) {  // 遍历数组 a
        if (sum + a[i] < 0)         // 如果当前累加和小于 0，则重置 sum 为 0
            sum = 0;
        else                        // 否则累加当前元素到 sum，并更新 ans 为最大值
            sum += a[i], ans = max(ans, sum);
    }
    cout << ans << '\n';          // 输出最大子段和
    return 0;                     // 程序正常结束
}

【实例 2】 StarryCoding P264 活动选择问题。在星码乐园中有 n 个活动，但遗憾的是只有一个活动大厅，同一时间只能进行一个活动，第 i 个活动的活动时间为 [li,ri)。请问最多能完成多少个活动？

输入格式：

第一行包含一个整数 T，表示测试用例的数量（1 ≤ T ≤ 10^3）。

对于每组测试用例：

第一行包含一个整数，表示 n（2 ≤ n ≤ 10^5）；
接下来 n 行，每行包含两个整数 li 和 ri（1 ≤ li < ri ≤ 10^9），表示活动 i 的时间；
数据保证 ∑n ≤ 2×10^5。

输出格式：

对于每组测试用例，输出一个整数，表示最多可以完成的活动数量。

样例输入：

2
3
1 5
2 3
3 7
2
1 5
2 4

样例输出：

2
1

在样例中，选择活动 2 和活动 3，可以完成两个活动。

解题思路：根据贪心的思路，我们选择一个活动时，应尽可能为后续的选择留下更大的空间。因此，当有多个活动可以选择时，应该选择结束时间最早的活动。

具体步骤如下：

将所有活动存入结构体，并按照结束时间 r 升序排序；
依次遍历活动，采用“能选即选”的策略（即如果当前活动的开始时间 l 不早于已选活动的结束时间，则选取该活动）；
统计选中的活动数量，即为最大活动数量。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;

struct Node {
    int l, r;
} a[N];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].l >> a[i].r;

    // 根据右端点排序，即按结束时间排序
    stable_sort(a + 1, a + 1 + n, [](const Node &u, const Node &v) {
        if (u.r != v.r) return u.r < v.r;
        return u.l < v.l;
    });

    int now = 0, ans = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i].l >= now) {
            ans++, now = a[i].r;
        }

    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

C++贪心算法的使用（附带实例）

相关文章