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

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

什么是贪心

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

常见的贪心问题

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

区间问题

区间覆盖

典型题例:

给定 N 个闭区间 [ai,bi] 以及一个线段区间 [s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。

输出最少区间数,如果无法完全覆盖则输出 −1。

示例 :

输入:第一行包含两个整数 s 和 t,表示给定线段区间的两个端点。
      第二行包含整数 N,表示给定区间数。
       接下来 N 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。
1 5
3
-1 3
2 4
3 5
输出:
2

思路:左端点排序 + 贪心决策

  1. 将所有区间按照左端点从小到大进行排序
  2. 从前往后枚举每个区间,在所有能覆盖start的区间中,选择右端点的最大区间,然后将start更新成右端点的最大值(贪心决策);

代码:

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n;
struct Range{
    int l, r;
    bool operator< (const Range&w) const {
        return l < w.l;
    }
} ranges[N];
int main() {
    int st, ed;
    scanf("%d%d", &st, &ed);
    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);
    int ans = 0;
    bool success = false;
    for (int i= 0; i < n; i ++) {
        int j = i, r = -2e9;
        while (j < n && ranges[j].l <= st) {  //找到所有左端点<=st的区间右端点最大的点
            r = max(r, ranges[j].r); 
            j ++;
        }
        if (r < st) {  //肯定有空隙
            ans = -1;
            break;
        }
        ans ++;
        if (r >= ed) {
            success = true;
            break;
        }
        st = r;  //更新st
        i = j - 1;  //
    }
    if (!success)  ans = -1;
    printf("%d", ans);
}

Huffman树

合并果子

典型题例:

在一个果园里,达达已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。达达决定把所有的果子合成一堆。每一次合并,达达可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。

可以看出,所有的果子经过 n−1 次合并之后,就只剩下一堆了。达达在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家,所以达达在合并果子时要尽可能地节省体力。

假定每个果子重量都为 1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使达达耗费的体力最少,并输出这个最小的体力耗费值。

例如有 3 种果子,数目依次为 1,2,9。可以先将 1、2 堆合并,新堆数目为 3,耗费体力为 3。

接着,将新堆与原先的第三堆合并,又得到新的堆,数目为 12,耗费体力为 12。

所以达达总共耗费体力=3+12=15。

可以证明 15 为最小的体力耗费值。

示例 :

输入:输入包括两行,第一行是一个整数 n,表示果子的种类数。
      第二行包含 n 个整数,用空格分隔,第 i 个整数 ai 是第 i 种果子的数目。。
3 
1 2 9 
输出:
15

思路

  1. 使用小根堆维护所有果子,每次弹出堆顶的两堆果子,并将其合并,合并之后将两堆重量之和再次插入小根堆中。
    代码:
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int main() {
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> heap;  //小根堆
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        heap.push(x);
    }
    int ans = 0;
    while (heap.size() > 1) {  //堆的个数大于1就需要合并
        int a = heap.top(); heap.pop();
        int b = heap.top(); heap.pop();
        ans += a + b;
        heap.push(a + b);
    }
    printf("%d", ans);
    return 0;
}

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

充电站

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

相关文章
PCIe锁定事务(Locked Transactions)介绍
PCIe锁定事务(Locked Transactions)介绍
1525 0
PCIe锁定事务(Locked Transactions)介绍
|
2月前
|
人工智能 缓存 安全
阿里云最新版通义千问大模型全功能解析:百万上下文+全模态Agent企业落地指南
随着生成式AI技术持续迭代,阿里云通义千问完成多轮基座升级,形成覆盖旗舰高性能、均衡通用、高速轻量、全模态视听理解的完整模型家族,不再局限简单问答对话,进化成具备长文本深度理解、多模态感知、自主智能体执行、工程级代码开发能力的通用AI底座,面向普通个人用户、独立开发者、中小企业以及大型政企提供分层能力输出,既可以网页端直接交互使用,也可以通过阿里云百炼平台API接口集成到业务系统,还支持开源权重本地私有化部署,适配不同层级业务诉求。
2024 1
|
4月前
|
Web App开发 前端开发 API
GPT5.6凌晨刚上线:三档模型怎么选,别把额度烧在Sol上
GPT5.6上线,推出Sol/Terra/Luna三档模型:Sol专攻复杂任务,Terra适配日常办公,Luna专注快速批量处理。搭配GPT-Live全双工语音、桌面端Work/Codex整合及限额透明化,强调“按需选模”而非盲目用强。工具越智能,越需人精准定义目标与分工。(239字)
|
5月前
|
存储 人工智能 安全
阿里云服务器经济型e实例2核2G、2核4G、4核8G等配置解析:实例性能、适用场景与活动价格参考
阿里云经济型e实例是面向个人开发者、学生及小微企业的入门级云服务器,2核2G3M带宽仅99元/年,热门配置享3.9折起优惠。产品采用Intel Xeon处理器,支持ESSD Entry云盘,具备企业级SLA与安全标准,国内32个可用区广泛售卖。适用于AI智能体轻载部署、个人学习测试、中小型网站搭建、开发测试环境及轻量级企业应用等场景。
|
7月前
|
监控
企业 Agent 落地后,为什么多模型需求会跟着出来
企业Agent天然是分层链路,理解、规划、执行、校验等环节对模型能力要求各异。单模型难兼顾成本、稳定与治理,多模型分工(强模决策、轻模执行、独立校验)+统一入口,才是落地刚需。
|
7月前
|
存储 人工智能 安全
意图共鸣科技:AI记忆链的优雅降级——算力可以断,记忆不能断
《AI记忆链商业化白皮书》提出“优雅降级”方案:解耦算力与记忆,实现“算力可断、记忆不断”。记忆空间独立付费、永久保留,支持随时查看、导出与管理;算力按需购买,恢复即无缝续聊。让AI如停机保号般可靠。
496 7
|
7月前
|
人工智能 缓存 资源调度
AI数字人系统开发全流程:源码选型 + 部署 + 商业化指南
本文从实战角度系统拆解AI数字人项目的完整开发流程,涵盖源码选型策略、系统部署架构设计以及主流商业化路径。针对企业与开发团队在落地过程中常见的成本控制、性能优化与变现模式问题,提供可执行的解决思路,帮助读者从“能跑Demo”迈向“可持续盈利”的数字人业务体系。
|
8月前
|
人工智能 运维 安全
资产类型转移:面向意图编程与AI时代的组织重构
本文提出“资产类型主导组织形态”核心观点:互联网公司困局源于以“代码”为核心资产,而AI时代应转向“意图+约束”新资产。面向意图编程(IOP)将业务目标显性化为意图、技术规范可执行化为约束,推动组织从职能分层流水线,升级为意图定义者、约束设计师等角色协同的市场式协作,实现知识资产化、复用自动化、质量内建化。(239字)
|
11月前
|
缓存 并行计算 Shell
毅硕HPC | 在HPC集群上优雅地使用conda
通过本教程,你将掌握在HPC集群中从零开始部署并高效利用Conda的核心技能。为你的课题创建一个干净的environment.yml文件,让你的科研计算之旅更加规范、高效和可复现。
1000 0
|
12月前
|
人工智能 自然语言处理 搜索推荐
AI数字人技术力盘点:数字人平台技术实力、产品实测、市场口碑综合推荐
2025年,AI数字人爆发:克拉玛依“小克”上线,罗永浩数字人6小时带货5500万。IDC数据显示,中国AI数字人市场规模2024年达41.2亿元,增速85.3%。世优科技以全栈技术打造1200+数字人IP,赋能政务、文旅等场景;科大讯飞依托语音优势,让“数字大圣”多语互动;微软小冰聚焦明星IP,孵化洛天依等虚拟偶像。从技术深耕到IP运营,三巨头各展所长,推动数字人从概念走向规模化落地,重塑商业未来。
609 0