贪心算法 - 常见的问题总结(一)

简介: 贪心算法 - 常见的问题总结(一)

什么是贪心

贪心:贪心在解决问题上是目光短浅的,仅仅根据当前的已知信息就做出选择,并且一旦做了选择,就不再更改

常见的贪心问题

  1. 区间问题
  2. Huffman树
  3. 排序不等式
  4. 绝对值不等式
  5. 推公式

区间问题

区间选点

典型题例:

给定 N 个闭区间[ai,bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内

示例 :


         

思路

  1. 将每个区间按照右端点从小到大进行排序
  2. 从前往后枚举区间,end值初始化为无穷小
  • 如果本次区间不能覆盖掉上次区间的右端点, ed < range[i].l
  • 说明需要选择一个新的点, res ++ ; ed = range[i].r;
    证明顺序
  • 证明ans<=cnt :cnt 是一种可行方案, ans是可行方案的最优解,也就是最小值。
  • 证明ans>=cnt : cnt可行方案是一个区间集合,区间从小到大排序,两两之间不相交。所以覆盖每一个区间至少需要cnt个点。

代码:


         

区间分组

典型题例:

给定 N 个闭区间[ai,bi],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。

输出最小组数。

示例 :


         

思路

  1. 把所有区间按照左端点从小到大排序
  2. 从前往后枚举每个区间,判断此区间能否将其放到现有的组中 l[i] > Max_r
  • 不能,就开一个新组,这里就是在小根堆中加入一个点,小根堆维护得是每个组得右端点得最大值;堆顶维护得最小堆。
  • 能,就加入该组并更新该组右端点。
  1. heap有多少区间,就有多少组

代码:

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n;
struct Range {
  int l, r;
  bool operator< (Range& w) const {
      return l < w.l;
  }
} ranges[N];
int main() {
    scanf("%d", &n);
    //处理输入
    for (int i = 0; i < n; i ++) {
        int l, r;
        scanf("%d%d", &l, &r);
        ranges[i] = {l, r};
    }
    sort(ranges, ranges + n);
    //小根堆的每个节点都是每组的右端点的,堆定(根节点)维护的是最小组的右端点
    priority_queue<int, vector<int>, greater<int>> heap;
    for (int i = 0; i < n; i ++) {
        if (heap.empty() || heap.top() >= ranges[i].l) heap.push(ranges[i].r);  //与最小组的最大右值有冲突
        else {
            heap.pop();
            heap.push(ranges[i].r);
        }
    }
    printf("%d", heap.size());  //堆的大小就是最小的分组
    return 0;
}

传送门:贪心算法 - 常见的问题总结(二)

充电站

推荐一个零声学院免费公开课程,个人觉得老师讲得不错,分享给大家:Linux,Nginx,ZeroMQ,MySQL,Redis,fastdfs,MongoDB,ZK,流媒体,CDN,P2P,K8S,Docker,TCP/IP,协程,DPDK等技术内容,立即学习

相关文章
|
3月前
|
人工智能 文字识别 API
阿里云百炼大模型视觉类模型有哪些?可选模型及能力、适用场景和最新活动介绍
本文介绍了阿里云百炼平台视觉类大模型的完整矩阵与选型策略。平台集成通义千问(Qwen)全系列自研视觉模型及DeepSeek、Kimi等第三方模型,涵盖旗舰推理(Qwen3.8-Max)、均衡型(Qwen3.6-Plus)、高性价比(Qwen-Flash)、专用OCR与视觉推理(QVQ)、开源及第三方等多条产品线,覆盖图像理解、生成、OCR、视频分析等场景。
|
开发框架 .NET 程序员
驾驭Autofac,ASP.NET WebApi实现依赖注入详细步骤总结
Autofac 是一个轻量级的依赖注入框架,专门为 .NET 应用程序量身定做,它就像是你代码中的 "魔法师",用它来管理对象的生命周期,让你的代码更加模块化、易于测试和维护
914 4
驾驭Autofac,ASP.NET WebApi实现依赖注入详细步骤总结
|
文字识别 测试技术 API
实战阿里通义灵码极速编程-截屏-OCR-Ollama篇代码
该代码实现了一个截屏测试工具,结合了鼠标事件监听、屏幕截图和OCR功能。用户可通过拖动鼠标选择屏幕区域进行截图,并将截图转换为Markdown格式的文本内容。具体步骤包括:初始化大模型客户端、编码图像为Base64格式、捕获指定屏幕区域并保存截图、调用大模型API进行OCR识别并输出Markdown格式的内容。
880 9
|
存储 人工智能 算法
技术经验分享:7z命令行压缩解压详解
技术经验分享:7z命令行压缩解压详解
3732 0
|
弹性计算 网络协议 文件存储
将Windows系统机器加入AD域
一台Windows服务器需要加入到Active Directory域后才能通过AD域服务来管理。本文介绍了如何将一台Windows服务器加入已有的AD域。
5782 0
将Windows系统机器加入AD域
|
机器学习/深度学习 人工智能 自然语言处理
探索深度学习中的注意力机制:原理、应用与未来展望
探索深度学习中的注意力机制:原理、应用与未来展望
|
存储 安全 网络安全
数据库安全措施有哪些?
【8月更文挑战第15天】数据库安全措施有哪些?
1358 1
|
Ubuntu Linux Docker
Docker容器运行时权限和Linux系统功能
Docker容器运行时权限和Linux系统功能 相关Docker参数 --cap-add: Add Linux capabilities --cap-drop: Drop Linux capabilities --privileged=false: Give extended privileges...
11566 0
|
人工智能 运维 Serverless
30 秒出服装设计稿,森马用函数计算+AIGC 整“新活”!
阿里云函数计算帮助森马应对AI项目初期的决策周期长、自建GPU集群成本高和模型部署难的挑战,通过提供一键部署的Stable Diffusion模型,实现快速的AI推理应用开发和部署。
167472 13