CSP-J 复赛算法 贪心算法练习

前言

在CSP-J复赛中，算法题目常常要求选手不仅具备基本的编程能力，还需要灵活运用多种算法来高效解决问题。而贪心算法作为一种常见且有效的算法思路，在竞赛中具有极其重要的地位。贪心算法的核心思想是通过每一步都采取当前最优的策略，期望通过一系列的局部最优选择达到全局最优解。虽然贪心算法无法保证所有问题都能得到最优解，但在某些特定问题上，如最小生成树、最短路径、任务调度等，它却可以提供高效且准确的解法。

本文将通过复赛中可能遇到的贪心算法问题进行分析与实践，帮助选手更好地理解贪心算法的应用场景和解题思路。

纪念品分组

洛谷：P1094

贪心算法的分析过程

1. 排序：先将所有纪念品的价格按照从小到大的顺序排序。这样可以方便地使用贪心策略，将最贵的和最便宜的纪念品配对。

2. 双指针法：用两个指针，i 指向最便宜的纪念品（从头开始），j 指向最贵的纪念品（从尾开始）。我们尝试将这两个物品进行配对：

   • 如果 P[i] + P[j] <= w，说明这两个纪念品可以放在一组，此时 i 向右移动，j 向左移动。
   • 如果 P[i] + P[j] > w，说明最贵的物品无法与当前的最便宜物品配对，只能单独分为一组，此时只移动 j。

3. 停止条件：当两个指针相遇时，所有纪念品都已经被分配完毕。

通过以上步骤，能够保证分组数目最少，因为贪心策略使得每个物品都尝试与最优的配对进行组合。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm> // 用于排序

using namespace std;

int main() {
    int w, n;
    
    // 输入上限 w 和纪念品总数 n
    cin >> w >> n;
    
    vector<int> prices(n);
    
    // 输入每个纪念品的价格
    for (int i = 0; i < n; ++i) {
        cin >> prices[i];
    }
    
    // 1. 先对价格进行升序排序
    sort(prices.begin(), prices.end());
    
    // 2. 双指针初始化
    int i = 0, j = n - 1;
    int groups = 0;
    
    // 3. 开始贪心分组
    while (i <= j) {
        if (prices[i] + prices[j] <= w) {
            // 如果最便宜和最贵的可以放在一组
            ++i; // i 向右移动
        }
        // 无论能否配对，j 始终左移，代表最贵的物品已处理
        --j;
        
        // 分组数增加
        ++groups;
    }
    
    // 输出最少的分组数目
    cout << groups << endl;
    
    return 0;
}

代码解析

1. 输入与初始化：

   • 首先读取每组的价格上限 w 和纪念品总数 n。
   • 使用 vector<int> 存储所有纪念品的价格。

2. 排序：

   • 使用 C++ 标准库的 sort 函数将纪念品的价格按升序排列。这是为了方便使用贪心策略，便于最便宜的和最贵的物品配对。

3. 双指针法：

   • i 指向价格数组的起始位置，j 指向终止位置。
   • 每次检查价格最贵的纪念品 prices[j] 是否能与最便宜的纪念品 prices[i] 配对。
   • 如果可以配对，两者都从队列中移除（即 i++ 和 j--），否则只移除最贵的（j--），并将其单独分为一组。

4. 输出结果：

   • 最后，输出分组的总数。

泥泞路

这道题是一个典型的贪心算法问题，要求最少的木板数目来覆盖所有的泥泞路段。我们可以通过以下步骤解决该问题：

分析过程

1. 整理数据

我们有多段泥泞路，每一段都有起点 s 和终点 e。每一块木板的长度为 L，要覆盖所有泥泞路的区间。

2. 合并区间

如果有些泥泞路段是重叠的或相邻的，可以先对这些泥泞路段进行合并，这样可以减少木板的使用。为了方便处理，先将所有泥泞路按照起点 s 排序，然后依次检查当前的泥泞路段和上一个泥泞路段是否有重叠或者相邻，进行合并处理。

什么叫做合并区间

合并区间（Merge Intervals）是指在一组区间中，如果某些区间存在重叠或相邻的部分，将它们合并为一个连续的区间，从而减少不必要的重复处理。常见的合并区间问题需要先对区间进行排序，然后依次检查区间是否可以合并。

例子说明

假设有以下泥泞路段（区间）：

(1, 5), (4, 9), (12, 15), (14, 18)

这些区间可以通过以下步骤进行合并：

1. 排序区间

首先，将这些区间按照起点排序（如果已经是有序的可以跳过这一步）。得到：

(1, 5), (4, 9), (12, 15), (14, 18)

2. 逐个检查区间是否可以合并

• 从第一个区间 (1, 5) 开始，检查下一个区间 (4, 9)。
  • 由于 (4, 9) 的起点 4 小于等于 (1, 5) 的终点 5，所以这两个区间是重叠的，可以合并成一个更大的区间 (1, 9)。
• 继续检查下一个区间 (12, 15)：
  • 这个区间的起点 12 大于前一个合并后区间 (1, 9) 的终点 9，说明它们不重叠，因此无法合并，保留 (12, 15)。
• 检查下一个区间 (14, 18)：
  • 由于 (14, 18) 的起点 14 小于等于 (12, 15) 的终点 15，所以可以将它们合并成一个更大的区间 (12, 18)。

3. 最终的合并结果

合并后的区间结果为：

(1, 9), (12, 18)

这样，我们通过合并区间将原来有重叠的部分减少，得到了两个合并后的连续区间。

合并区间的算法思路

1. 排序：首先将所有区间按照起点进行排序。
2. 合并逻辑：
   • 设当前区间为 current_interval，从头开始遍历区间。
   • 如果下一个区间的起点在当前区间的范围内（即下一个区间的起点小于等于 current_interval 的终点），则这两个区间有重叠，合并为新的区间，更新 current_interval 的终点。
   • 否则，保存当前区间，并开始处理下一个区间。

伪代码

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>>& intervals) {
    // 先按照区间起点排序
    sort(intervals.begin(), intervals.end());

    vector<pair<int, int>> result;
    pair<int, int> current_interval = intervals[0];

    for (int i = 1; i < intervals.size(); ++i) {
        // 如果当前区间和下一个区间重叠
        if (intervals[i].first <= current_interval.second) {
            // 合并区间，更新当前区间的终点
            current_interval.second = max(current_interval.second, intervals[i].second);
        } else {
            // 不重叠，保存当前区间并开始处理下一个区间
            result.push_back(current_interval);
            current_interval = intervals[i];
        }
    }

    // 最后一个区间也需要保存
    result.push_back(current_interval);

    return result;
}

例子代码说明

假设输入的区间为：

vector<pair<int, int>> intervals = {{1, 5}, {4, 9}, {12, 15}, {14, 18}};

执行上述代码后，合并后的区间将会是：

{{1, 9}, {12, 18}}

合并区间的实际应用

1. 日程安排：如果有很多会议需要安排，要求找到所有重叠的会议时间，进行合并，避免冲突。
2. 道路覆盖：如题目所述，如果有很多泥泞路段，使用木板覆盖这些路段时，可以通过合并相邻的区间减少木板的使用。

3. 计算木板数

合并之后的每一段泥泞路，我们可以通过贪心的方式用尽量少的木板进行覆盖。每段泥泞路的长度可以通过 (e - s) 来计算，而所需的木板数就是该段长度除以木板长度 L，如果有余数，还需要一块额外的木板。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Mud {
    int start, end;
};

bool compareMud(const Mud &a, const Mud &b) {
    return a.start < b.start;
}

int main() {
    int n, L;
    cin >> n >> L;
    
    vector<Mud> muds(n);
    
    // 输入泥泞路段的起点和终点
    for (int i = 0; i < n; ++i) {
        cin >> muds[i].start >> muds[i].end;
    }
    
    // 按照起点排序
    sort(muds.begin(), muds.end(), compareMud);
    
    int totalPlanks = 0;
    int currentPos = 0;
    
    for (int i = 0; i < n; ++i) {
        // 如果当前泥泞路段和上一个没有相交
        if (currentPos < muds[i].start) {
            currentPos = muds[i].start;
        }
        
        // 计算当前泥泞路段还需要覆盖的长度
        while (currentPos < muds[i].end) {
            totalPlanks++;
            currentPos += L;
        }
    }
    
    cout << totalPlanks << endl;
    
    return 0;
}

代码解释

1. 数据输入: 首先读取输入的 n 和 L，然后将每段泥泞路的起点和终点存入结构体 Mud 中。

2. 排序: 按照泥泞路的起点进行排序，以便我们能依次处理每段泥泞路并进行合并。

3. 计算木板数:

   • 初始化 currentPos 作为当前木板的铺设位置。
   • 对于每一段泥泞路，如果当前铺设位置小于泥泞路的起点，则将铺设位置更新为泥泞路的起点。
   • 计算需要多少木板才能覆盖这段泥泞路，并更新铺设位置。

4. 输出结果: 最后输出最少需要的木板数目。

样例分析

输入:

3 3
1 6
13 17
8 12

1. 将泥泞路段按照起点排序：

   (1, 6), (8, 12), (13, 17)
   

2. 计算覆盖 1-6 的泥泞路：

   • 需要至少两块长度为 3 的木板，1-6 可以被 2 块木板覆盖。

3. 计算覆盖 8-12 的泥泞路：

   • 需要至少两块长度为 3 的木板，8-12 可以被 2 块木板覆盖。

4. 计算覆盖 13-17 的泥泞路：

   • 需要至少一块木板覆盖 13-16，再加上一个 1km 的部分，也需要两块木板。

输出:

5

总结

通过对CSP-J复赛中常见的贪心算法问题的探讨和分析，我们可以发现贪心算法在许多场景下都能够快速且高效地找到解法。尽管贪心算法的局限性在于它依赖于问题的特殊性质来保证正确性，但当问题满足贪心选择性质时，它往往能以较低的时间复杂度找到最优解。在实际比赛中，正确识别问题的贪心特性并快速设计出合理的解法是提升解题效率的关键。选手们需要多加练习，培养在复杂问题中应用贪心算法的敏锐度，从而在竞赛中脱颖而出。