当前位置：首页 > news >正文

算法学习笔记之贪心算法

news 来源：原创 2025/5/12 5:49:10

导引（硕鼠的交易）

硕鼠准备了M磅猫粮与看守仓库的猫交易奶酪。

仓库有N个房间，第i个房间有 J[i] 磅奶酪并需要 F[i] 磅猫粮交换，硕鼠可以按比例来交换，不必交换所有的奶酪

计算硕鼠最多能得到多少磅奶酪。

输入M和N表示猫粮数量和房间数量，随后输入N个房间，每个房间包括奶酪数和猫粮数

Input

 5 37 24 35 2-1 -1

Output

 13.333

解法：计算每个房间的奶酪与猫粮之比，比值越大硕鼠收益越高，将所有比值从大到小排序，最后选择比值大的即可。

例1（田忌赛马）

问题描述：田忌与齐王赛马，每匹马的速度不同。

目标：赢得最多的比赛。

策略：利用田忌的最弱的马去对齐王的最强的马，反之亦然。

不要固定认为是将田忌第一强的马与齐王第二强的马进行比较，因为可能田忌第一强的马比齐王第一强的马更强

经典贪心（事件序列问题）

命题：至少存在一个最长的事件序列，包含最早结束的事件

采用反证法证明：假设有一个最长的事件序列bcdef，不包含最早结束的事件a，显然a在b之前结束，那么事件序列acdef依旧是最短事件序列。

显然，选中最早结束的事件对最长的事件序列无影响。

那么，我们可以选中最早结束的事件0，然后再选中发生时刻大于等于3，且结束时刻最小的事件；

继续选中事件1，然后再选中发生时刻大于等于4，且结束时刻最小的事件；

继续选中事件5，然后再选中发生时刻大于等于10，且结束时刻最小的事件；

继续选中事件8，然后再选中发生时刻大于等于15，且结束时刻最小的事件；

继续选中事件10，然后发现没有可选事件了，最长事件序列为0,1,5,8,10

贪心思路：先把所有事件按结束时刻从大到小排序，随后每次选择一个最早结束且和之前不冲突的事件

例2（搬桌子）

一层楼的布局如上，现在需要将一些桌子从一个房间搬到另一个房间。无论距离远近，每趟搬运都需要十分钟。

当你从房间 i 搬桌子到房间 j 时，房间 i 到房间 j 的走廊被占用，也就是同一时间的走廊是互斥的。

现在需要计算完成所有搬运任务最少需要多长时间。

输出包含T组用例。首先输入一个正整数N，表示需要搬运的桌子数，接下来N行，每行包含2个正整数a和b，表示需要将桌子从a房间搬到b房间

输出为每组用例搬运任务需要的最少时间。

思路：记录每段区间的走廊被占用的次数，重合的次数就是需要搬运的次数

 #include<iostream>using namespace std;int t, i, j, N, P[200]; int s, d, temp, k, MAX;int main(){cin >> t;for(i = 0; i < t; i++){// 初始化 for(j = 0; j < 200; j++){P[j] = 0;}cin >> N;for(j = 0; j < N; j++){cin >> s >> d;s = (s-1)/2;d = (d-1)/2;if(s > d){swap(s, d);}for(k = s; k <= d; k++){P[k]++;}}MAX = -1;for(j = 0; j < 200; j++){MAX = max(MAX, P[j]);}cout << MAX*10 << endl;}return 0;}

例3（删数问题）

思路：显然高位越小越好。每次比较相邻两数，若左边比右边大则删去左边的数，否则继续比较后面的数。

例4（青蛙的邻居）

输入t组样例，每组样例先输入n个湖泊，每个青蛙呆在不同湖泊里面，然后输入n青蛙的邻居个数，问能否根据这些数据构成一个图。

问题本质：可图性判断

1、度序列：若把图G所有顶点的度数排成一个序列S，则称S为图G的度序列。

2、序列是可图的：一个非负整数组成的有限序列如果是某个无向图的度序列，则称该序列是可图的。

算法：Havel-Hakimi定理

由非负整数组成的非增序列S：d1 , d2, ... dn(n >= 2, d1 >= 1)是可图的，当且仅当序列S1：d2-1, d3-1, ..., dd1+1-1, dd1+2, ... ,dn是可图的。

其中，序列S1中有n-1个非负整数，S序列中d1后的前d1个度数(即d2 ~ dd1+1)减 1 后构成S1中的前d1个数。

通俗理解：

假设有一群人的邻居数为递增序列 5 4 4 3 2 1 1，若该序列成立，则第一个人有5个邻居，假设第一个人的五个邻居分别是2,3,4,5,6

当第一个人搬走了，剩下的人邻居个数为 3 3 2 1 0 1；排序后为为3 3 2 1 1 0

当第二个人搬走了，剩下的人邻居个数为 2 1 0 1 0；排序后为为2 1 1 0 0

当第三个人搬走了，剩下的人邻居个数为 0 0 0 0，此时该序列成立。

特别说明：若要用贪心算法求解某问题的整体最优解，必须首先证明贪心思想在该问题的应用结果就是最优解！！

sort函数的使用

头文件

 #include<algorithm>

函数用法

sort(首地址，尾地址+1，cmp函数);

当不传入cmp函数时，默认递增

例：

 struct node{int a;double b;}arr[100];// 要求先按a升序，若a相等则按b降序bool cmp(node x, node y){if(x.a != y.a){return x.a < y.a;}return x.b > y.b;}

算法学习笔记之贪心算法

导引（硕鼠的交易） 硕鼠准备了M磅猫粮与看守仓库的猫交易奶酪。仓库有N个房间，第i个房间有 J[i] 磅奶酪并需要 F[i] 磅猫粮交换，硕鼠可以按比例来交换，不必交换所有的奶酪计算硕鼠最多能得到多少磅奶酪。输入M和…...

编程日记 2025/5/12 5:49:10

【数据结构】(8) 二叉树

一、树形结构 1、什么是树形结构根节点没有前驱，其它节点只有一个前驱（双亲/父结点）。所有节点可以有 0 ~ 多个后继，即分支（孩子结点）。每个结点作为子树的根节点，这些子树互不相交。 2、关于…...

编程日记 2025/5/12 4:41:48

前端大屏适配方案：从设计到实现的全流程指南

引言随着数据可视化需求的增长，大屏展示项目在前端开发中越来越常见。然而，大屏开发面临独特的挑战： 屏幕分辨率多样：从1080P到4K甚至8K，如何保证清晰度？布局复杂：多图表、多组件如何合理排列…...

编程日记 2025/5/12 4:36:28

10. Hbase Compaction命令

一. 什么是Compaction 在 HBase 中，频繁进行数据插入、更新和删除操作会生成许多小的 HFile，当 HFile 数量增多时，会影响HBase的读写性能。此外，垃圾数据的存在也会增加存储需求。因此，定期进行 Compact操作&#xff…...

编程日记 2025/5/12 4:56:51

完善sql盲注中的其他函数 dnslog+sqlmap外带数据

2. 布尔盲注布尔盲注是通过观察应用程序的响应（如页面内容、HTTP 状态码等）来判断查询条件是否为真。 <?php // 数据库连接配置 $host localhost; $dbname testdb; $user root; $password password; // 创建数据库连接 $conn new mysqli($ho…...

编程日记 2025/5/12 5:06:49

Python 识别图片和扫描PDF中的文字

目录工具与设置 Python 识别图片中的文字 Python 识别图片中的文字及其坐标位置 Python 识别扫描PDF中的文字注意事项在处理扫描的PDF和图片时，文字信息往往无法直接编辑、搜索或复制，这给信息提取和分析带来了诸多不便。手动录入信息不仅耗时费…...

编程日记 2025/5/12 5:35:00

Java 有哪些锁，他们的区别是什么

Java 锁的分类 Java 中的锁可以从多个维度进行分类： 悲观锁 vs. 乐观锁公平锁 vs. 非公平锁独占锁 (互斥锁) vs. 共享锁 (读写锁)可重入锁 vs. 不可重入锁自旋锁偏向锁 vs. 轻量级锁 vs. 重量级锁 (JVM 锁优化) 1. synchronized 关键字： 类型: 悲观锁…...

编程日记 2025/5/12 5:21:51

CSS实现单行、多行文本溢出显示省略号（…）

在网页设计中，我们常常遇到这样的情况：文本内容太长，无法完全显示在一个固定的区域内。为了让界面看起来更整洁，我们可以使用省略号（…）来表示内容溢出。这不仅能提升用户体验，还能避免内容溢出…...

编程日记 2025/5/12 4:08:16

网络协议/MQTT Paho.MQTT客户端库接口基础知识

开源c版mqtt客户端：https://github.com/eclipse-paho/paho.mqtt.cMQTT 客户端与服务器之间支持的通信协议主要包括：协议地址格式加密默认端口适用场景服务器地址示例TCPtcp://不加密1883局域网或对安全性要求不高的场景tcp://localhost:1883TLS/SSLssl://加密8883对安全性要…...

编程日记 2025/5/12 5:02:20

VSCode C/C++ 开发环境完整配置及常见问题（自用）

这里主要记录了一些与配置相关的内容。由于网上教程众多，部分解决方法并不能完全契合我遇到的问题，因此我选择以自己偏好的方式，对 VSCode 进行完整的配置，并记录在使用过程中遇到的问题及解决方案。后续内容也会持续更新和完善。…...

编程日记 2025/5/12 5:29:35

深入解析 Go 中的 `io.Pipe()`：实现高效的并发通信

在 Go 语言中，io.Pipe() 是一个强大且灵活的工具，用于在不同的 goroutine 之间实现高效的同步和通信。它通过创建一对连接的 I/O 流，允许数据在管道的两端安全地传递。本文将详细介绍 io.Pipe() 的工作原理、主要特点、使用方法以及一些实际应…...

编程日记 2025/5/12 4:25:35

【Kubernetes】常用命令全解析：从入门到实战（中）

🐇明明跟你说过：个人主页 🏅个人专栏：《Kubernetes航线图：从船长到K8s掌舵者》 🏅 🔖行路有良友，便是天堂🔖 目录一、引言 1、什么是k8s 2、K8s的核心功能二、资…...

编程日记 2025/4/23 15:56:18

嵌入式八股文面试题（二）C语言算法

相关概念请查看文章：C语言概念。 1. 如何实现一个简单的内存池？ 简单实现： #include <stdio.h> #include <stdlib.h>//内存块 typedef struct MemoryBlock {void *data; // 内存块起始地址struct MemoryBlock *next; // 下一个内…...

编程日记 2025/5/7 11:35:54

Proxmox VE 8.3 qm 方式导入ESXi Linux OVA UEFI模式虚拟机

前言实现esxi ova uefi 虚拟机导入到pve，Linux UEFI 都支持创建一个105虚拟机 qm 参数使用参考，以下可以根据自己的实际情况执行调整 esxi 导出虚拟机参考 #vmid (100 - 999999999) vmid=105# qm vm name...

编程日记 2025/5/12 5:12:16

人工智能浪潮下脑力劳动的变革与重塑：挑战、机遇与应对策略

一、引言 1.1 研究背景与意义近年来，人工智能技术发展迅猛，已成为全球科技领域的焦点。从图像识别、语音识别到自然语言处理，从智能家居、智能交通到智能医疗，人工智能技术的应用几乎涵盖了我们生活的方方面面，给人…...

编程日记 2025/5/11 2:39:42

【线性代数】1行列式

1. 行列式的概念行列式的符号表示：行列式的计算结果：一个数计算模型1：二阶行列式二阶行列式：三阶行列式： n阶行列式： 🍎计算行列式计算模型2：上三角形行列式上三角形行列式特征：主对角线下皆为0。上三角形行列式：化上三角形通用方法：主对角线下，…...

编程日记 2025/5/11 21:36:04

厘米和磅的转换关系

在排版和设计领域，厘米（cm）和磅（pt）都是常用的长度度量单位，它们之间的转换关系基于特定的换算标准，下面为你详细介绍： 基本换算关系磅是印刷行业常用的长度单位，1英寸…...

编程日记 2025/5/12 5:14:26

vant4 van-list组件的使用

<van-listv-if"joblist && joblist.length > 0"v-model:loading"loading":finished"finished":immediate-check"false"finished-text"没有更多了"load"onLoad">// 加载 const loading ref(fals…...

编程日记 2025/5/9 7:48:34

QT 异步编程之多线程

一、概述 1、在进行桌面应用程序开发的时候，假设应用程序在某些情况下需要处理比较复制的逻辑，如果只有一个线程去处理，就会导致窗口卡顿，无法处理用户的相关操作。这种情况下就需要使用多线程，其中一个线程处理窗口事…...

编程日记 2025/5/12 5:13:18

HCIA项目实践---OSPF的知识和原理总结

9.5 OSPF 9.5.1 从哪些角度评判一个动态路由协议的好坏？ （1）选路佳（是否会出环） OSPF 协议采用链路状态算法，通过收集网络拓扑信息来计算最短路径，从根本上避免了路由环路的产生。 &#xff08…...

编程日记 2025/5/12 5:10:09

DNS污染：网络世界的“隐形劫持”与防御

在互联网的底层架构中，DNS（域名系统）如同数字世界的“导航员”，将用户输入的域名翻译成机器可读的IP地址。然而，DNS污染（DNS Poisoning）正像一场无声的“地址篡改”危机，威胁着全球网…...

编程日记 2025/5/12 4:00:45

Shader Feature 设置Keyword //0:Red 1:Green 2:Blue Mat.SetInt(“_Color”,0); 需要在创建时进行设置，运行时不可设置 Shader "Unlit/KeywordEnum" {Properties{[KeywordEnum(Red,Green,Blue)] _Color("Color",int) 0}SubShader{Pass{HLSL…...

编程日记 2025/5/9 20:55:45

Java-数据结构-栈与队列(常考面试题与单调栈)

在上一篇的学习中，我们学习了栈和队列的基本知识，以及它们对应都有哪些方法，在什么应用场景下如何使用，并且还对它们进行了模拟实现，而其实对于栈和队列的相关知识还远不止于此，而今天我们就对栈与队列进行…...

编程日记 2025/5/7 9:18:57

Python Pandas（11）：Pandas 数据可视化

数据可视化是数据分析中的重要环节，它帮助我们更好地理解和解释数据的模式、趋势和关系。通过图形、图表等形式，数据可视化将复杂的数字和统计信息转化为易于理解的图像，从而便于做出决策。Pandas 提供了与 Matplotlib 和 Seaborn 等可视化库…...

编程日记 2025/5/12 4:14:50

wordpress模板文件结构超详解

wordpress网站建设中，主题的制作是最为核心的环节。了解模板文件结构是模板制作的第一步，本文所讲的模板文件结构包括两部分，一是指以文件名为概念的文件结构，二是指文件内容的代码结构。一、如何使模板文件起作用 ↑ wordpres…...

编程日记 2025/5/12 5:27:29

大脑神经网络与机器神经网络的区别

大脑神经网络（生物神经网络）与机器神经网络（人工神经网络，ANN）虽然名称相似，但在结构、功能、学习机制等方面存在显著差异。以下是两者的主要区别： 1. 基础结构与组成大脑神经网络：由生物神经元（约860亿个）通过突触连接形成动态网络。神经元通过电化学信号（动作…...

编程日记 2025/5/12 5:30:39

【H5自适应】高端科技类pbootcms网站模板 – 三级栏目、下载与招聘功能支持

(H5自适应)高端大气的科技类pbootcms网站模板带三级栏目、下载和招聘功能后台地址：您的域名/admin.php 后台账号：admin 后台密码：123456 为了提升系统安全，请将后台文件admin.php的文件名修改一下。修改之后，后台…...

编程日记 2025/5/12 4:54:46

SQL-leetcode—1661. 每台机器的进程平均运行时间

1661. 每台机器的进程平均运行时间表: Activity ----------------------- | Column Name | Type | ----------------------- | machine_id | int | | process_id | int | | activity_type | enum | | timestamp | float | ----------------------- 该表展示了一家工厂网站的…...

编程日记 2025/5/12 5:42:39

C++ Primer 跳转语句

欢迎阅读我的【CPrimer】专栏专栏简介：本专栏主要面向C初学者，解释C的一些基本概念和基础语言特性，涉及C标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级…...

编程日记 2025/5/12 0:17:12

清华大学：DeepSeek 如何赋能职场应用（35 页 PDF）

原来已经分享过清华大学的 DeepSeek：从入门到精通（100页PDF） 现在又来第二弹：《DeepSeek 如何赋能职场应用？从提示语技巧到多场景应用》 PDF里介绍了 DeepSeek 这一人工智能工具及其在职场中的应用，从基础…...

编程日记 2025/5/9 15:01:08

idea 错误: 找不到或无法加载主类 @C:\Users\admin\AppData\Local\Temp\idea_arg_file1549212448

idea 错误: 找不到或无法加载主类 C:\Users\admin\AppData\Local\Temp\idea_arg_file1549212448 该错误往往和左下角爱弹出的如下提示是一个意思 Error running ‘PayV3Test1.testTransferBatchesBatchId’ Error running PayV3Test1.testTransferBatchesBatchId. Command lin…...

编程日记 2025/5/1 12:42:54

开发指南098-logback-spring.xml说明

可执行的工程src\main\resources目录有logback-spring.xml文件用于配置日志。配置日志有些容易犯晕的地方，这里列出： 1、<logger>标签的优先级高于<root>标签‌：所以，如果<logger>标签指定了某个具体的包或类的…...

编程日记 2025/5/1 12:43:57

【SpringBoot3.x+】slf4j-log4j12依赖引入打印日志报错的两种解决方法

最开始引入了1.7.5版本的slf4j-log4j依赖包，但是控制台不报错也不显示日志在https://mvnrepository.com/找到最新的2.0.16版本之后出现报错： 进入提示的slf4j网站中可以找到从2.0.0版本开始，slf4j-log4j已经被slf4j-reload4j取代&#xff1…...

编程日记 2025/5/7 18:25:49

【STM32】H743的以太网MAC控制器的一个特殊功能

调试743的MAC，翻阅手册的时候，发现了一个有意思的功能混杂模式 H743的MAC控制器，可以设置为混杂模式，这就意味着它可以做一些网络监控的应用，譬如连接具备端口镜像功能的交换机，然后直接代替PC实现网络数据…...

编程日记 2025/5/8 2:23:29

Java LinkedList(单列集合)

LinkedList 是 Java 中实现了 List 接口的一个类，它属于 java.util 包。与 ArrayList 不同，LinkedList 是基于双向链表实现的，适合于频繁进行插入和删除操作的场景。 1. LinkedList 的基本特性基于链表实现：LinkedList 使用双向…...

编程日记 2025/5/7 17:34:39

docker compose快速部署kafka-connect集群

先部署kafka集群，启动参考：docker compose部署kafka集群-CSDN博客创建timezone文件，内容填写Asia/Shanghai 再部署kafka-connect集群 networks: net: external: true services: kafka-connect1: restart: always image:…...

编程日记 2025/5/11 17:43:35

docker 部署nginx，nginx 504

遇到问题原因： 因为用的docker 部署nginx, docker 应用与服务之间的端口未开放，导致访问不到服务。...

编程日记 2025/5/11 5:54:59

RealClip正式发布：重新定义轻量化数字内容交互体验

在移动互联网流量红利逐渐见顶的当下，用户对即时性、碎片化娱乐与交互体验的需求持续攀升。轻量化小游戏、VR互动、数字孪生、工业仿真等内容形态迅速崛起，但开发者却面临两大核心矛盾：如何将高性能互动内容轻量化嵌入现有应用中？…...

编程日记 2025/5/6 8:42:21

SQLMesh系列教程-2：SQLMesh入门项目实战（上篇）

假设你已经了解SQLMesh是什么，以及其他应用场景。如果没有，我建议你先阅读《SQLMesh系列教程-1：数据工程师的高效利器-SQLMesh》。在本文中，我们将完成一个小项目或教程，以帮助你开始使用SQLMesh。你可以选择一步一步…...

编程日记 2025/5/9 14:29:35

把 DeepSeek1.5b 部署在显卡小于4G的电脑上

这里写自定义目录标题介绍准备安装 Ollama查看CUDA需要版本安装CudaToolkit检查Cuda是否装好设置Ollama环境变量验证是否跑在GPU上ollama如何导入本地下载的模型安装及配置docker安装open-webui启动open-webui开始对话调整gpu精度介绍 Deepseek1.5b能够运行在只用cpu和gpu内…...

编程日记 2025/5/6 5:49:21

#渗透测试#批量漏洞挖掘#29网课交单平台 SQL注入

免责声明本教程仅为合法的教学目的而准备，严禁用于任何形式的违法犯罪活动及其他商业行为，在使用本教程前，您应确保该行为符合当地的法律法规，继续阅读即表示您需自行承担所有操作的后果，如有异议，请立即停止本文章读。目录 1. 漏洞原理 2. 漏洞定位 3. 攻击验证示…...

编程日记 2025/5/5 9:55:34

试试DeepSeek写prompt+stable diffusion生成漫画

#deepseek #stable diffusion 模型：dreamshaperXL_v21TurboDPMSDE.safetensors 一、情节拟定漫画情节由deepseek自编自导，画幅为四张。 Prompt 1: 魔法觉醒 "一个平凡的少年在阁楼发现一本古老的魔法书，书页散发着微弱的蓝光。画…...

编程日记 2025/5/6 0:25:36

java面试题之 int和Integer的区别

int和Integer的区别 1、Integer是int的包装类，int则是java的一种基本数据类型 2、Integer变量必须实例化后才能使用，而int变量不需要 3、Integer实际是对象的引用，当new一个Integer时，实际上是生成一个指针指向此对象&#xff1b…...

编程日记 2025/5/11 3:00:22

Spring Bean的生命周期

1、对象实例化 2、属性设置 3、初始化 4、使用 5、销毁示例代码如下： import org.springframework.stereotype.Component;Component public class SpringBeanA {public SpringBeanA() {System.out.println("第一步：实例化(spring对象&#x…...

编程日记 2025/5/10 15:47:21

Vue 发送 PDF 文件链接到 WinForm 程序进行打印

Vue 发送 PDF 文件链接到 WinForm 程序进行打印的完整流程如下： 1. Vue 端 Vue 通过 fetch 或 axios 发送 PDF 文件的 URL 给 WinForms 程序（WinForms 需要开启一个本地 API）。 <template><div><button click"sendPri…...

编程日记 2025/5/11 15:56:15

Vue笔记（十）

一、AI的基本认知二、ChatGPT的基本使用三、AI插件--Copilot入门 1.Copilot是由OpenAI和GitHub合作开发的AI编程辅助插件，基于大量代码训练，能根据上下文自动生成代码建议。 2.安装与配置：在常用代码编辑器（如Visual Studio Cod…...

编程日记 2025/5/7 4:39:21

使用LangChainV3.0加载PDF文件并进行总结

LangChain目前已经更新到了V3版本，之前一直使用的V1版本，有很多方法都需要自己去封装，这次重新看了V3版本的API文档，很多方法都十分便利，调用方法简单明了十分方便，下面就来展示下这次对于PDF文件加载的优化…...

编程日记 2025/5/5 2:59:44

玩转大语言模型——使用Kiln AI可视化环境进行大语言模型微调数据合成

系列文章目录玩转大语言模型——使用langchain和Ollama本地部署大语言模型玩转大语言模型——三分钟教你用langchain提示词工程获得猫娘女友玩转大语言模型——ollama导入huggingface下载的模型玩转大语言模型——langchain调用ollama视觉多模态语言模型玩转大语言模型—…...

编程日记 2025/5/9 18:04:57

EasyRTC智能硬件：小体积，大能量，开启音视频互动新体验

在万物互联的时代，智能硬件正以前所未有的速度融入我们的生活。然而，受限于硬件性能和网络环境，许多智能硬件在音视频互动体验上仍存在延迟高、卡顿、回声等问题，严重影响了用户的使用体验。 EasyRTC智能硬件，凭借其强…...

编程日记 2025/5/9 2:14:58

vue知识点5

1.如何让组件里的样式与其他组件互相不干扰 scope范围的意思 <style scope> </style> 2.vue的生命周期创建挂载更新销毁 3.vue的四个生命周期详解创建beforeCreate,created 挂载 beforeMount,mounted 更新 beforeUpdate,updated 销毁 beforeDest…...

编程日记 2025/5/10 10:54:21