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

贪心算法

news 来源：原创 2025/9/17 22:59:39

int a[1000], b=5, c=8;
swap(b, c); // 交换操作
memset(a, 0, sizeof(a)); // 初始化为0或-1

引导问题

为一个小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆，第i个房间有J[i] 磅的五香豆，并且需要用F[i]磅的猫粮去交换；求老鼠最多可换多少豆？若五香豆不能全换猫粮，按比例换。

Sample Input
5 3 ——M猫粮 N房间
7 2 ——五香豆猫粮
4 3
5 2
-1 -1 —— 结束

Sample Output
13.333

由按比例换，7/2=3.5 4/3=1.333... 5/2=2.5 3.5最大排序，一次换——7+5+1.3333=13.333

初识贪心

在对问题求解时，总是做出在当前看来是最好的选择。

也就是说，不从整体上加以考虑，所作出的仅仅是在某种意义上的局部最优解（是否是全局最优，需要证明）。

例题

1.田忌赛马

每个马跟比自己弱的程度最小的马

1.排序

2.蓝色最大和红色最大比较，看蓝色能不能比过红色，若比不过，拿蓝色最小的跟红色比

3.拿蓝色最大跟红色第二大的比...能比就比，不能就继续拿最差的跟最好的比

反证法上大分~事件序列问题

已知N个事件的发生时刻和结束时刻。

一些在时间上没有重叠的事件，可以构成一个事件序列，如事件{2，8，10}。

事件序列包含的事件数目，称为该事件序列的长度。

请编程找出一个最长的事件序列。

至少存在一个最长事件序列包含最早结束事件（最早结束事件是0）

反证法证明上句：

假设所有最长事件序列都不包含最早结束事件；只要证明这个假设是错的，原命题得证；

任取一个所谓的最长事件序列，把第一个事件去掉，换掉事件0，肯定跟后面都不冲突（因为换上的是最早结束的时间，原来都不冲突，现在更不冲突）

证明完后选中最早结束事件0 后面我做类似的：每次找一个最早结束的事件，只要和前面的不冲突的都选中；

2.搬桌子

一个公司要做调整搬桌子，房间有400个，一边是单号，一边双号；

走廊很窄，只通过1个桌子过；

输入：

第二行：趟数

第三行：房间号：10号搬到20号

每趟搬要10min：不重叠可以同时搬，要10min；重叠要分开搬

法一：与上题的思想差不多，只不过，改成了最早开始事件（找开始最早的）

法二：统计每个区间在时间轴上的重叠次数，并找出最大重叠次数的区间。

#include <bits/stdc++.h>
using namespace std;int main() {int t, i, j, N, P[200];  // t是测试用例的数量，N是每个测试用例的区间数量int s, d, temp, k, MAX;  // s和d是区间的起点和终点，MAX用于记录最大重叠次数cin >> t;for (i = 0; i < t; i++) {// 初始化P数组，用于记录每个时间点的重叠次数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) {temp = s;s = d;d = temp;}// 在区间[s, d]内的每个时间点增加计数for (k = s; k <= d; k++)P[k]++;}// 找到最大重叠次数MAX = -1;for (j = 0; j < 200; j++)if (P[j] > MAX)MAX = P[j];// 输出最大重叠次数乘以10cout << MAX * 10 << endl;}return 0;
}

3.删数问题

已知一个长度不超过240位的正整数n（其中不含有效字0），去掉其中任意s（s小于n的长度）个数字后，将剩下的数字按原来的左右次序组成一个新的正整数。

给定n和s，请编程输出最小的新正整数。

Sample Input
178543 4
Sample Output
13

法一：从左到右扫描逆序对，删掉左边的数，若没有逆序对，删掉最后一位数

1 7 8 5 4 3 —— 1 7 5 4 3 ——1 5 4 3 ——1 4 3 —— 1 3

1 2 3 4

4.青蛙的邻居

每个湖泊都有一个青蛙，如果两个湖泊之间有水渠相连，我们认为两个青蛙他们为邻居；

问：你可以画出这个湖泊分布图吗？

Sample Input

3

7 —— 青蛙个数

4 3 1 5 4 2 1 —— 第一个青蛙有4个邻居；第二个青蛙有3个邻居....

6

4 3 1 4 2 0

6

2 3 1 1 2 1

Sample Output

YES

NO

YES

用以下知识可解决：

离散数学：可图性判定

两个概念：

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

度：一个顶点他有几条边，度就是几

2 3 1 1 1 就是度序列

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

若度序列2 3 1 1 1可以画出图A，就是可图的；

Havel-Hakimi定理：解决可读性判定

之后再排序：3 2 2 2 1

做一趟，排序一次；只要出现负数，就不可能了，图画不出来；最后全变成0，可以画；

Havel定理的解释——加加减减与图的对应关系_哔哩哔哩_bilibili

特别说明

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

在使用贪心算法解决问题时，必须首先证明贪心策略能够导致整体最优解。贪心算法通常通过每一步选择局部最优解来构建全局解，但并非所有问题都适合使用贪心算法，因此证明其正确性是关键。

说明理由：

若某货币系统有三种币值，分别为一角、五分和一分；要找1角5分
求最小找币数时，是否可以用贪心法求解？

可以；先用最大的能找几个找几个；

如果将这三种币值改为一种一分、五分和一分；要找1角5分

是否还可以使用贪心法求解？

不行；

因为他不成倍数；

贪心算法的常见操作：

贪心总是要找最大的、最小的、最划算的，往往要排序；

贪心算法

int a[1000], b5, c8; swap(b, c); // 交换操作 memset(a, 0, sizeof(a)); // 初始化为0或-1 引导问题为一个小老鼠准备了M磅的猫粮，准备去和看守仓库的猫做交易，因为仓库里有小老鼠喜欢吃的五香豆，第i个房间有J[i] 磅的五香豆&#xf…...

编程日记 2025/9/17 22:59:39

如何查询网站是否被百度蜘蛛收录？

一、使用site命令查询这是最直接的方法。在百度搜索框中输入“site:你的网站域名”，例如“site:example.com”（请将“example.com”替换为你实际的网站域名）。如果搜索结果显示了你的网站页面，并且显示了收录的页面数量&#xf…...

编程日记 2025/9/13 19:46:02

Hutool - Log：自动识别日志实现的日志门面

一、简介在 Java 开发中，日志记录是一项非常重要的功能，它可以帮助开发者在开发和生产环境中监控程序的运行状态、排查问题。然而，Java 生态系统中有多种日志实现框架，如 Log4j、Logback、JDK 自带的日志框架等。为了在不同的项…...

编程日记 2025/9/13 19:46:00

【GPU驱动】- 状态机

一、概述 Mesa 是一个开源的图形库，它提供了一个通用的图形抽象层，支持多种硬件和驱动程序。Mesa 的核心组件之一是 State Tracker，它在抽象图形 API（如 OpenGL ）与具体的图形驱动之间起到桥梁作用。State Tracker 通…...

编程日记 2025/9/15 20:08:39

rtcwake - Linux下定时唤醒计算机

rtcwake 是一个用于通过实时时钟（RTC）唤醒计算机的工具。它常用于在 Linux 系统中设置计算机在指定时间自动唤醒或关闭。以下是对命令 rtcwake -m off -s ${sleep_time} 的详细解析： 命令解析 bash复制 rtcwake -m off -s ${sleep_time} 1…...

编程日记 2025/9/17 20:30:20

MySQL 日志

MySQL 日志慢查询日志(Slow query log) 慢查询⽇志由执⾏时间超过系统变量 long_query_time 指定的秒数的SQL语句组成，并且检查的⾏数⼤于系统变量 min_examined_row_limit 指定值。被记录的慢查询需要进⾏优化， 可以使⽤mysqldumpslow客⼾端程序对慢…...

编程日记 2025/9/17 22:56:39

C++ 泛型编程之补充(class 和typename)

目录 1.class 和 typename 可互换 1.1 template 和 template 在模板参数列表中完全一样，可以互换使用。 2.什么时候 class 和 typename 不一样？ 2.1 嵌套依赖类型时必须用typename 重点说明： 2.2 普通作用域（不能互换&…...

编程日记 2025/9/15 8:35:55

[MDM 2024]Spatial-Temporal Large Language Model for Traffic Prediction

论文网址：[2401.10134] Spatial-Temporal Large Language Model for Traffic Prediction 论文代码：GitHub - ChenxiLiu-HNU/ST-LLM: Official implementation of the paper "Spatial-Temporal Large Language Model for Traffic Prediction" …...

编程日记 2025/9/13 19:45:51

跟着 Lua 5.1 官方参考文档学习 Lua (6)

文章目录 2.11 – Coroutines 2.11 – Coroutines Lua supports coroutines, also called collaborative multithreading. A coroutine in Lua represents an independent thread of execution. Unlike threads in multithread systems, however, a coroutine only suspends i…...

编程日记 2025/9/15 17:12:14

Spring Cloud — Hystrix 服务隔离、请求缓存及合并

Hystrix 的核心是提供服务容错保护，防止任何单一依赖耗尽整个容器的全部用户线程。使用舱壁隔离模式，对资源或失败单元进行隔离，避免一个服务的失效导致整个系统垮掉（雪崩效应）。 1 Hystrix监控 Hystrix 提供了对服务…...

编程日记 2025/9/13 19:45:47

加油站(力扣134)

既然每一个加油站都有对应的加油量和耗油量，我们不妨计算一下每个加油站的汽油净增量。如果每个加油站净增量之和不为负数，则说明一定可以找到唯一的起始点。那我们该如何找到这个起始点呢？我们设置最开始的起点为第0个加油站，接着…...

编程日记 2025/9/13 19:45:45

科普：你的笔记本电脑中有三个IP：127.0.0.1、无线网 IP 和局域网 IP；两个域名：localhost和host.docker.internal

三个IP 你的笔记本电脑中有三个IP：127.0.0.1、无线网 IP 和局域网 IP。在不同的场景下，需要选用不同的 IP 地址，如下为各自的特点及适用场景： 127.0.0.1（回环地址） 特点 127.0.0.1 是一个特殊的 IP 地…...

编程日记 2025/9/16 10:52:31

Golang 相关的github 开源项目

1. pan-light url: http://github.com/peterq/pan-lightstar: 12.1kfork: 2.5kwatch: 284 用Golang和Qt5编写的不限速版百度网盘。相比之前版本的百度网盘客户端，当前版本拥有更友好、便捷的图形界面，体量更轻，便于使用，只需下载…...

编程日记 2025/9/13 9:34:02

数据结构《图》

数据结构《图论》图的性质一、无向图（Undirected Graph） 定义由一组顶点（Vertex）和一组无向边（Edge）构成。每条无向边用一条无方向的线段连接两个顶点，记为 ( (u, v) )，其中…...

编程日记 2025/9/16 8:20:26

WPF实现打印机控制及打印

在WPF中实现打印机控制和打印功能，通常需要使用System.Printing命名空间中的类来管理打印机和打印任务。以下是一个简单的示例，展示如何在WPF应用程序中实现打印功能。 1. 添加必要的引用首先，确保在项目中引用了System.Printing命名空间。…...

编程日记 2025/9/15 21:47:13

springboot系列十四: 注入Servlet, Filter, Listener + 内置Tomcat配置和切换 + 数据库操作

文章目录注入Servlet, Filter, Listener官方文档基本介绍使用注解方式注入使用RegistrationBean方法注入DispatcherServlet详解内置Tomcat配置和切换基本介绍内置Tomcat配置通过application.yml完成配置通过类配置切换Undertow 数据库操作 JdbcHikariDataSource需求分析应用…...

编程日记 2025/9/13 19:45:36

DeepSeek 助力 Vue 开发：打造丝滑的二维码生成（QR Code）

前言：哈喽，大家好，今天给大家分享一篇文章！并提供具体代码帮助大家深入理解，彻底掌握！创作不易，如果能帮助到大家或者给大家一些灵感和启发，欢迎收藏关注哦 💕 目录 Deep…...

编程日记 2025/9/13 19:45:33

从传统到轻量级5G：网络架构演变与优化路径

轻量级5G 随着5G技术的不断发展，通信网络架构正经历着前所未有的变革。传统的5G核心网架构虽然在性能和容量方面表现出色，但在灵活性、部署效率以及成本控制方面却面临一些挑战。为了应对日益复杂的通信需求，轻量级5G核心网成为了一种…...

编程日记 2025/9/16 7:54:57

独立开发者如何寻找产品设计灵感

作为独立开发者，面对激烈的市场竞争和不断变化的用户需求，寻找优秀的产品设计灵感是至关重要的一步。以下是一篇关于独立开发者如何寻找产品设计灵感的教程，希望能为你提供一些有益的指导。一、观察日常生活 1.1 关注身边的小问题在日常生…...

编程日记 2025/9/13 19:45:30

技术解析 | 适用于TeamCity的Unreal Engine支持插件，提升游戏构建效率

龙智是JetBrains授权合作伙伴、Perforce授权合作伙伴，为您提供TeamCity、Perforce Helix Core等热门的游戏开发工具及一站式服务 TeamCity 是游戏开发的热门选择，大家选择它的原因包括支持 Perforce、可以进行本地安装，并提供了多种配置选项。…...

编程日记 2025/9/16 6:38:36

uniapp h5端和app端使用 turn.js

前提:添加页后,添加页与当前页会重叠在一起,不知道为什么,没有找到解决办法 1.h5端 <template><view class"container"><view id"flipbook"><view class"page page1">Page 1</view><view class"page pag…...

编程日记 2025/9/13 19:45:26

智慧校园系统在学生学习与生活中的应用

随着科技的快速发展，智慧校园系统逐渐成为现代教育不可或缺的一部分。它整合了先进的信息技术、物联网技术以及人工智能等，旨在构建一个全面、智能、个性化的学习与生活环境。对于学生而言，这一系统不仅能够极大地提高学习效率，还…...

编程日记 2025/9/13 19:45:24

umi: valtio的使用

一、基本用法 import { proxy, useSnapshot } from umijs/max;// 1、定义数据 const state proxy({ count: 33 });export default () > {// 2、使用数据const snap useSnapshot(state);function increaseCount() {state.count 1;}return (<><h1>{snap.count}…...

编程日记 2025/9/11 9:29:32

什么是矩阵账号？如何高效运营tiktok矩阵账号

‍‌‌‌‌‍‌‌‌‍‌‌‌‍‌‌‌‍‌‌‌‌‌‌‍‌‌‌‍‌‌‌‌‍‌‌‌‍‌‌‌‌‌‍‌‌‌‌‍‌‌‌‌‌‍‌‌‌‌‌‍‌‌‌‌‌‍‌‌‌‌‍‌…...

编程日记 2025/9/15 9:17:44

C语言.h头文件的写法

头文件的内容 #ifndef __SEQUENCE_LIST_H // 定义以防止递归包含 #define __SEQUENCE_LIST_H // (1)、其它头文件 #include <stdio.h> #include <stdlib.h> #include <strings.h> #include <stdbool.h> // (2)、宏定义(函数、变量、常量) // (3)、…...

编程日记 2025/9/14 17:15:04

【Day44 LeetCode】图论问题 Ⅱ

一、图论问题 Ⅱ 1、岛屿的最大面积这题和上一篇博客求岛屿数量如出一辙，都是要找出所有岛屿，深度优先搜索代码如下： # include<iostream> # include<vector>using namespace std;int dfs(vector<vector<int>> …...

编程日记 2025/9/15 8:26:44

设计模式教程：责任链模式（Chain of Responsibility Pattern）

责任链模式（Chain of Responsibility Pattern）是一种常用的设计模式，它属于行为型模式，主要解决的是多个对象处理一个请求时，如何解耦请求的发送者和接收者，以及如何将请求的处理职责分配给不同的对象。 1…...

编程日记 2025/9/11 14:12:40

java网络编程

计算机网络基础网络编程的目的就是直接或间接地通过网络协议与其他计算机进行通信。在 Java 语言中包含网络编程所需要的各种类，编程人员只需要创建这些类的对象，调用相应的方法，就可以进行网络应用程序的编写。要进行网络程序的编写&am…...

编程日记 2025/9/14 0:14:58

计算机网络面试知识点总结

目录 1. 计算机网络的基本知识点2. OSI 七层模型3. TCP/IP 四层模型4. TCP 和 UDP4.1 TCP 协议4.2 TCP 流量控制4.3 TCP 拥塞控制4.4 TCP 三次握手4.5 TCP 四次挥手4.6 TCP 粘包问题4.7 TCP Socket交互流程4.8 UDP 协议以及和 TCP 协议的不同 5. HTTP协议5.1 HTTP 请求方法以及…...

编程日记 2025/9/13 15:19:59

ubuntu22.4搭建单节点es8.1

下载对应的包 elasticsearch-8.1.1-linux-x86_64.tar.gz 创建es租户 groupadd elasticsearc useradd elasticsearch -g elasticsearch -p elasticsearch chmod uw /etc/sudoers chmod -R elasticsearch:elasticsearch elasticsearch 修改配置文件 vim /etc/sysctl.conf vm…...

编程日记 2025/9/15 18:21:27

卷积与动态特征选择：重塑YOLOv8的多尺度目标检测能力

文章目录 1. YOLOv8的网络结构概述2. 添加注意力机制2.1 为什么添加注意力机制？2.2 如何将注意力机制集成到YOLOv8中？2.3 效果分析 3. C2f模块的集成3.1 C2f模块简介3.2 如何在YOLOv8中集成C2f模块？3.3 效果分析 4. 卷积操作的优化4.1 卷积操…...

编程日记 2025/9/12 8:22:50

【Altium Designer】差分对等长设置以及绕线

在Altium Designer 17中设置差分对的等差规则及绕等长操作，需结合规则配置与交互式布线工具完成。以下是详细操作步骤： 目录一、差分对等差规则设置 1. 原理图端差分对定义 2. PCB端差分规则配置二、差分对等长绕线操作 1. 差分对布线 2. 交互式…...

编程日记 2025/9/14 15:57:29

BFS 和 DFS（深度优先搜索、广度优先搜索）

深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法，用于解决图相关的问题。它们在搜索问题中具有广泛的应用，如路径搜索、连通性检测等。以下是具体区别： （图片引自&am…...

编程日记 2025/9/15 10:00:43

汽车免拆诊断案例 | 2013 款奔驰 S300L 车起步时车身明显抖动

故障现象　一辆2013款奔驰S300L车，搭载272 946发动机，累计行驶里程约为15万km。车主反映，将挡位置于D挡，稍微释放一点制动踏板，车辆蠕动时车身明显抖动，类似气缸失火时的抖动，又类似手动变速器…...

编程日记 2025/9/14 20:24:13

基于UnrealEngine(UE5)的太空探索

视频部分可参见：https://www.bilibili.com/video/BV1JWA8eSEVg/ 中国天宫号空间站人造卫星可视化星链卫星可视化小行星分布及运动轨迹可视化月球基地可视化八大行星轨道太阳系宜居带可视化阿波罗8号拍摄的地球升起谷神星模型及轨迹可视化星座可视化十…...

编程日记 2025/9/14 20:25:11

HTML Application(hta)入门教程

简介 HTA是HTML Application的缩写，又称为HTML应用程序。 hta是一个可执行文件，双击可以直接运行 hta与html非常相似，可直接将文件后缀改为.hta来获得HTA格式的文件。支持VBS和JavaScript html的权限被限制在网页浏览器内，只有操…...

编程日记 2025/9/14 20:10:25

IOS UITextField 无法隐藏键盘问题

设置UITextField 键盘按钮返回键为“完成”，即return key 设置done .m代码设置代理 //设置代理协议 UITextFieldDelegate， self.mobileTextField.delegate self; ///点击完成键隐藏键盘 - (BOOL)textFieldShouldReturn:(UITextField *)textField{//取…...

编程日记 2025/9/14 18:48:24

ES6箭头函数：基础与进阶指南

目录引言一、基础篇：核心语法与特性 1.1 语法革新 1.2 this绑定机制二、进阶篇：深度特性解析 2.1 闭包中的this继承 2.2 限制与注意事项三、实践指南：应用场景与陷阱规避 3.1 推荐使用场景 3.2 应避免的场景四、性能考量结语…...

编程日记 2025/9/15 5:04:34

AI赋能编程：PyCharm与DeepSeek的智能开发革命

在这个智能化的时代，人工智能技术正在深刻地改变着我们的工作方式，尤其是在编程领域。无论是初学者还是资深开发者，都希望借助更高效的工具和智能助手来提升生产力、优化代码质量。今天，我们将聚焦于两个强大的工具：Py…...

编程日记 2025/9/15 1:14:57

在Spring Boot中如何使用Freemaker模板引擎

在 Spring Boot 中使用 FreeMarker 模板引擎可以帮助你创建动态的 Web 页面。以下是详细的步骤和示例代码，介绍如何在 Spring Boot 项目里集成和使用 FreeMarker。 1. 添加依赖如果你使用的是 Maven 项目，需要在 pom.xml 文件中添加 FreeMarker 相关依赖。Spring Boot 提供…...

编程日记 2025/9/13 19:45:22

【论文精读】VLM-AD：通过视觉-语言模型监督实现端到端自动驾驶

论文地址： VLM-AD: End-to-End Autonomous Driving through Vision-Language Model Supervision 摘要人类驾驶员依赖常识推理来应对复杂多变的真实世界驾驶场景。现有的端到端（E2E）自动驾驶（AD）模型通常被优化以模仿…...

编程日记 2025/9/16 3:46:24

【HarmonyOS Next】鸿蒙应用进程和线程详解

【HarmonyOS Next】鸿蒙应用进程和线程详解一、前言进程的定义： 进程是系统进行资源分配的基本单位，是操作系统结构的基础。在鸿蒙系统中，一个应用下会有三类进程： (1) 主进程， (2) ExtensionAbility进程&#xff…...

编程日记 2025/9/13 19:45:18

基于深度学习的信号滤波：创新技术与应用挑战

一、引言 1.1 研究背景随着科技的不断发展，信号处理领域面临着越来越复杂的挑战。在众多信号处理技术中，基于深度学习的信号滤波技术逐渐崭露头角，成为研究的热点。基于深度学习的信号滤波在信号处理领域具有至关重要的地位。如今&#…...

编程日记 2025/9/12 21:09:51

从【人工智能】到【计算机视觉】，【深度学习】引领的未来科技创新与变革

前几天偶然发现了一个超棒的人工智能学习网站，内容通俗易懂，讲解风趣幽默，简直让人欲罢不能。忍不住分享给大家，点击这里立刻跳转，开启你的AI学习之旅吧！ 前言 – 人工智能教程https://www.captainbed.cn/l…...

编程日记 2025/9/13 19:45:15

什么是方法

System.out.println(),那么它是什么呢？ Java方法是语句的集合，它们在一起执行一个功能。方法是解决一类问题的步骤的有序组合方法包含于类或对象中方法在程序中被创建，在其他地方被使用这段Java代码出现错误的原因在于，在…...

编程日记 2025/9/13 19:45:13

Python strip() 方法详解：用途、应用场景及示例解析（中英双语）

Python strip() 方法详解：用途、应用场景及示例解析在 Python 处理字符串时，经常会遇到字符串前后存在多余的空格或特殊字符的问题。strip() 方法就是 Python 提供的一个强大工具，专门用于去除字符串两端的指定字符。本文将详细介绍 strip(…...

编程日记 2025/9/13 8:41:01

合并区间（56）

56. 合并区间 - 力扣（LeetCode） 解法： class Solution { public:vector<vector<int>> merge(vector<vector<int>>& intervals) {if (intervals.size() 1) {return intervals;}//现根据每一项的第一个值&#…...

编程日记 2025/9/13 17:02:37