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

news/2024/10/7 14:17:48/

文章目录

  • 前言
  • 纪念品分组
    • 贪心算法的分析过程
    • C++ 代码实现
    • 代码解析
  • 泥泞路
    • 分析过程
      • 1. **整理数据**
      • 2. **合并区间**
        • 什么叫做合并区间
      • 例子说明
        • 1. **排序区间**
        • 2. **逐个检查区间是否可以合并**
        • 3. **最终的合并结果**
      • 合并区间的算法思路
      • 伪代码
      • 例子代码说明
      • 合并区间的实际应用
      • 3. **计算木板数**
    • 代码实现
    • 代码解释
    • 样例分析
  • 总结

前言

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


http://www.ppmy.cn/news/1535728.html

相关文章

图解C#高级教程（三）：泛型

图解C#高级教程（三）：泛型

本讲用许多代码示例介绍了 C# 语言当中的泛型&#xff0c;主要包括泛型类、接口、结构、委托和方法。 文章目录 1. 为什么需要泛型&#xff1f;2. 泛型类的定义2.1 泛型类的定义2.2 使用泛型类创建变量和实例 3. 使用泛型类实现一个简单的栈3.1 类型参数的约束3.2 Where 子句3…
阅读更多...
【MySQL】服务器管理与配置

【MySQL】服务器管理与配置

MySQL服务器 服务器默认配置 查看服务器默认选项和系统变量 mysqld --verbose --help 查看运行时的系统变量&#xff0c;可以通过like去指定自己要查询的内容 状态变量的查看 系统变量和状态变量的作用域 全局作用域&#xff1a; 对于每个会话都会生效当前会话&#xff1a;只…
阅读更多...
OpenJudge | 置换选择排序

OpenJudge | 置换选择排序

总时间限制: 1000ms 内存限制: 65536kB 描述 给定初始整数顺串&#xff0c;以及大小固定并且初始元素已知的二叉最小堆&#xff08;为完全二叉树或类似完全二叉树&#xff0c;且父元素键值总小于等于任何一个子结点的键值&#xff09;&#xff0c;要求利用堆实现置换选择排序&a…
阅读更多...
十四、深入理解Mysql索引底层数据结构与算法

十四、深入理解Mysql索引底层数据结构与算法

文章目录 一、索引的本质1、索引是帮助MySQL高效获取数据的排好序的数据结构2、索引的数据结构3、数据结构可视化网站 二、常见数据结构介绍1、B-Tree2、BTree&#xff08;B-Tree变种&#xff09;3、Hash结构 三、存储引擎的索引实现1、MyISAM存储引擎索引实现MyISAM索引文件和…
阅读更多...
Node.js env 环境变量多种配置方式

Node.js env 环境变量多种配置方式

目录 process.env 配置方式 dotenv 使用 cross-env process.env 在 Node.js 中&#xff0c;你可以使用 process.env 对象来读取环境变量。这个对象包含了所有的环境变量&#xff0c;你可以通过变量名来访问这些变量的值。 例如&#xff0c;如果你有一个名为 MY_VARIABLE …
阅读更多...
Element UI教程：如何将Radio单选框的圆框改为方框

Element UI教程：如何将Radio单选框的圆框改为方框

大家好&#xff0c;今天给大家带来一篇关于Element UI的使用技巧。在项目中&#xff0c;我们经常会用到Radio单选框组件&#xff0c;默认情况下&#xff0c;Radio单选框的样式是圆框。但有时候&#xff0c;为了满足设计需求&#xff0c;我们需要将圆框改为方框&#xff0c;如下…
阅读更多...
03.useToggler

03.useToggler

在 React 应用中，切换布尔状态是一个常见的需求，比如开关按钮、显示/隐藏元素等。useToggler 钩子提供了一种简洁而高效的方式来管理这种二元状态。这个自定义钩子不仅简化了代码，还提高了组件的可读性和可维护性。以下是如何实现和使用这个自定义钩子： const useToggler …
阅读更多...
佑航科技Pre-A+轮融资成功：加速车载超声波芯片研发与量产

佑航科技Pre-A+轮融资成功：加速车载超声波芯片研发与量产

近日，超声波芯片领域的领先企业珠海佑航科技有限公司（简称“佑航科技”）宣布成功完成数千万元的Pre-A+轮战略融资。本轮融资由上市公司思瑞浦微电子旗下的芯阳基金进行战略投资，标志着佑航科技在车载超声波芯片及传感器领域的研发与量产能力迈上了新台阶。此次融资不仅为佑…
阅读更多...
最新文章

Copyright @ 2022~2023