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

贪心算法笔记

news 来源：原创 2025/5/7 10:47:32

贪心算法笔记

大概内容

贪心就是对于一个问题有很多个步骤，我们在每一个步骤中都选取最优的那一个，最后得出答案。就是在一些函数中可行，但是有些比如二次函数，因为它的转折点不一定最优，就是不可行的。那么如何判断贪心呢？有这么几种

看时间复杂度，一般的就是 $O (n)$ 或者是排序 $\ log n)$
或者猜测，看着像就可以试试。
自己用数学证明方法，比如归纳法，交换法，就是如果交换之后答案变得小或者大就可以了。

那贪心在比赛中怎么办呢？可以先尝试一下大小样例，再尝试对拍，有个保底，如果可以也可以证明一下。

然后还有一种贪心，叫做反悔贪心，就是可以撤销，也没别的。

最后因为贪心每次取局部最优，所以代码不长，而且时间复杂度不大。

例题讲解

凌乱的yyy / 线段覆盖

题目大意:有 $n$ 个线段，问最多有多少个不重叠的线段。

思路：贪心，然后按照 $r_{i}$ 排序，每次选取尽可能早的场次并且要合法，也就是不能前面重叠。

证明：如果不相交，那么图片如下。

很明显，一场弄完，另一场。如果包含，图片如下：

那样我们就可以选择第一场，因为它结束得早，可以取另外的场次。所以证明取更早的是永远比更晚的要更优。

时间复杂度： $\log n)$

#include<bits/stdc++.h>
struct noip//有同学不会结构体的多开几个数组 
{int begin;//开始时间 int finish;//结束时间 
}a[2000005];
bool cmp(noip x,noip y)
{return x.finish<y.finish;//按结束时间排 
}
using namespace std;
int main()
{int n,ans=1;//初始化 cin>>n; for(int i=1;i<=n;i++){cin>>a[i].begin>>a[i].finish;}sort(a+1,a+n+1,cmp);//快速排序(不用我多说了吧) int mini=a[1].finish;//定义mini统计最后结束时间 int j=1;while(j<=n)//我用了while,感兴趣的同学可以用for(提示：for不用定义j) {j++;if(a[j].begin>=mini)//新的比赛开始时间要晚于mini {ans++;//统计比赛数 mini=a[j].finish;//更新mini }}cout<<ans<<endl;//输出 return 0;//功德圆满 
}

Teleporters (Easy Version)

思路：直接 $a_{i}+i$ 排序，就好了。

证明：就是每次都是走过去，传回来，所以直接排序就可以了。

时间复杂度： $\log n)$

#include<bits/stdc++.h>
using namespace std;
struct node
{int x,id;
}c[200005];
int n,m,tmp;
bool cmp(node a,node b)
{return a.x+a.id<=b.x+b.id;//跟思路一样排序
}
int main()
{int t;cin>>t;while(t--){memset(c,0,sizeof(c));cin>>n>>m;for(int i=1;i<=n;i++){cin>>tmp;c[i].x=tmp;c[i].id=i;}sort(c+1,c+n+1,cmp);int i=0;while(m>=0&&i<=n){i++;m=m-c[i].x-c[i].id;}cout<<i-1<<endl;	}return 0;
}

Teleporters (Hard Version)

思路：这一题就是先前缀和记录一下能用的传送门的价值之和，然后在使用二分答案，但是因为起点是 $0$ 的缘故，所以还要另外枚举 $0$ 点。

#include<bits/stdc++.h>
#define maxn 2900001
#define int long long
using namespace std;
int T,n,m,ans,a[maxn],s[maxn];
int check(int c,int x,int id)
{//二分最长的合法前缀区间int l=1,r=n,sum=-1;while(l<=r){int mid=l+r>>1;if(s[mid]-(mid>=id?x:0)<=c)sum=mid+(mid>=id?-1:0),l=mid+1;//特判x的影响else r=mid-1;}return sum==-1?0:sum;//可能无解
}
signed main()
{scanf("%lld",&T);while(T--){ans=0;map<int,int>mp;//记录位置scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);s[i]=min(a[i]+(n-i+1),a[i]+i);//取最小花费}sort(s+1,s+n+1);for(int i=1;i<=n;i++) mp[s[i]]=i,s[i]+=s[i-1];//前缀和for(int i=1;i<=n;i++){if(m-a[i]-i<0) continue;//可能不合法ans=max(ans,check(m-a[i]-i,min(a[i]+(n-i+1),a[i]+i),mp[min(a[i]+(n-i+1),a[i]+i)])+1);//注意要加上当前点i}printf("%lld\n",ans);}return 0;
}

国王游戏

思路:就是按照 $a_ib_i$ 的大小从小到大排序

证明：我们不妨设两个人分别写了 $a_1,b_1,a_2,b_2$ 且满足 $a_1b_1>a_2b_2$ 则有 $\tfrac{a_2}{b_1}=\tfrac{a_1}{b_2}$

所以有一下两种情况

1在2的前面
1在2的后面

设在设在 $1, 2$ 之前所有人左手乘积为 $k$ ，那么对于第一种情况，我们的答案就是

贪心算法笔记

贪心算法笔记大概内容贪心就是对于一个问题有很多个步骤，我们在每一个步骤中都选取最优的那一个，最后得出答案。就是在一些函数中可行，但是有些比如二次函数，因为它的转折点不一定最优，就是不可行的。那么如何判断贪心呢？有这么几种看时间复杂度，一般的就是 O ( n…...

编程日记 2025/5/7 10:47:32

切比雪夫插值

切比雪夫插值是一种基于切比雪夫节点的多项式插值方法，其优势是减少插值误差(特别是龙格现象：表现为高维插值时在边缘处插值误差骤增)。本文对其基本操作进行说明。 1. 切比雪夫节点切比雪夫插值的核心是使用切比雪夫节点作为插值点。切比雪夫节点是切…...

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

西电-神经网络基础与应用-复习笔记

此为24年秋研究生课程复习笔记导论神经网络的研究方法分为连接主义，生理学派，模拟神经计算。高度的并行、分布性，很强的鲁棒和容错性。便于实现人脑的感知功能(音频图像的识别和处理)。符号主义，心理学派，基于符号…...

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

【面试题】简单聊一下什么是云原生、什么是k8s、容器，容器与虚机相比优势

云原生（Cloud Native） 定义：云原生是一种构建和运行应用程序的方法，旨在充分利用云计算的优势。它涵盖了一系列技术和理念，包括容器化、微服务架构、自动化部署与管理等。特点：云原生应用程序被设计为可弹性…...

编程日记 2025/5/3 11:24:16

Vue 3 Diff 算法过程及基本实现方式

Vue 3 的 Diff 算法 Vue 3 使用的是一种高效的 DOM Diff 算法，主要用于在虚拟 DOM 树发生变化时，计算最小的操作以更新真实 DOM。相比 Vue 2，Vue 3 的 Diff 算法做了很多优化。 Diff 算法的背景与目的虚拟 DOM 树的对比：在 Vue…...

编程日记 2025/5/7 10:32:15

EasyCVR视频汇聚平台如何配置webrtc播放地址？

EasyCVR安防监控视频系统采用先进的网络传输技术，支持高清视频的接入和传输，能够满足大规模、高并发的远程监控需求。平台支持多协议接入，能将接入到视频流转码为多格式进行分发，包括RTMP、RTSP、HTTP-FLV、WebSocket-FLV、HLS、W…...

编程日记 2025/5/6 16:03:20

PowerApps助力PowerBI实现数据写回

原文发布日期: 2019-08-01 06:03:50 0000 注：本文旨在介绍Power BI如何利用PowerApps实现用户在前端对数据源进行增删查改，关于此，你也可以在Google上找到更详细但较零散的资料正文在SSAS多维数据集中，开发者可以给数据开启&q…...

编程日记 2025/5/6 9:22:17

数据结构：DisjointSet

Disjoint Sets意思是一系列没有重复元素的集合。一种常见的实现叫做，Disjoint-set Forest可以以接近常数的时间复杂度查询元素所属集合，用来确定两个元素是否同属一个集合等，是效率最高的常见数据结构之一。 Wiki链接：https://en…...

编程日记 2025/5/7 10:15:09

React 元素渲染

React 元素渲染 React 是一个用于构建用户界面的 JavaScript 库，它允许开发人员创建大型应用程序，这些应用程序可以随着时间的推移而高效地更新和渲染。React 的核心概念之一是元素渲染，它描述了如何将 JavaScript 对象转换为 DOM&#xff0…...

编程日记 2025/4/30 4:38:50

【Leetcode 每日一题】3270. 求出数字答案

问题背景给你三个正整数 n u m 1 num_1 num1， n u m 2 num_2 num2 和 n u m 3 num_3 num3。数字 n u m 1 num_1 num1， n u m 2 num_2 num2 和 n u m 3 num_3 num3 的数字答案 k e y key key 是一个四位数，定义如下&…...

编程日记 2025/5/7 10:13:58

eNSP之家----ACL实验入门实例详解（Access Control List访问控制列表）（重要重要重要的事说三遍）

ACL实验（Access Control List访问控制列表）是一种基于包过滤的访问控制技术，它可以根据设定的条件对接口上的数据包进行过滤，允许其通过或丢弃。访问控制列表被广泛地应用于路由器和三层交换机。准备工作在eNSP里面部署设备&a…...

编程日记 2025/5/7 10:20:01

【git】-2 分支管理

目录一、分支的概念二、查看、创建、切换分支 1、查看分支-git branch 2、创建分支- git branch 分支名 3、切换分支- git checkout 分支名三、git指针 -实现分支和版本间的切换四、普通合并分支 git merge 文件名五、冲突分支合并【git】-初始gi…...

编程日记 2025/5/7 10:25:37

硬件设计-齐纳管

目录摘要详情齐纳管的工作电流、摘要齐纳管（Zener Diode）是一种特殊的二极管，它能够在特定的反向电压下保持电流稳定。正常情况下，二极管只允许正向电流通过，而阻止反向电流流过。而齐纳管在一定的反向电压下可…...

编程日记 2025/5/7 9:49:10

Github出现复杂问题无法合并分支冲突太多如何复原

目录问题再现解决思路当然我所指的是在 main 分支开一个新的分支删除本地文件夹重新克隆开一个新分支切换分支下载远程分支文件覆盖合并到主分支问题再现太复杂了无法更改编译器现状全部崩溃了无法更改即使创建一个新的分支也无济于…...

编程日记 2025/5/7 10:26:57

《分布式光纤传感：架设于桥梁监测领域的 “智慧光网” 》

桥梁作为交通基础设施的重要组成部分，其结构健康状况直接关系到交通运输的安全和畅通。随着桥梁建设规模的不断扩大和服役年限的增长，桥梁结构的安全隐患日益凸显，传统的监测方法已难以满足对桥梁结构健康实时、全面、准确监测的需求。分布式…...

编程日记 2025/5/6 2:56:35

java_抽象类最佳实践-模板设计模式

基本介绍模板设计模式可解决的问题最佳实践 Template类 package com.hspedu.abstract_; abstract public class Template { //抽象类-模板设计模式public abstract void job();//抽象方法public void calculateTime() {//实现方法，调用 job 方法//得到开始的时间…...

编程日记 2025/5/7 9:51:42

linux网络 | http结尾、理解长连接短链接与cookie

前言：本节是http章节的最后一部分，主要解释一些小概念。讲解到了HTTP的方法，表单， 重定向等等。现在废话不多说， 开始我们的学习吧。 ps：本节内容都是概念， 知道就行， 友友们放心观…...

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

dtdug汇编指令练习

r 通用寄存器 m 代表内存 imm 代表立即数 r8 代表8位通用寄存器 m8 代表8位内存 imm8 代表8位立即数 mov指令练习 MOV 的语法: mov 目标操作数，源操作数作用:拷贝源操作数到目标操作数 1、源操作数可以是立即数、通用寄存器、段寄存器、或者内存单元. 2、目标操作数…...

编程日记 2025/5/7 10:03:19

Windows自动化Python pyautogui RPA操作

依赖包 import time import pyautogui import pyperclip import os import psutil from pywinauto.application import Application睡眠： pyautogui.sleep(1)鼠标事件： pyautogui.moveTo(100, 100, duration0.25) pyautogui.click(100, 100, duration0.…...

编程日记 2025/5/5 16:25:22

Ollama私有化部署大语言模型LLM

目录一、Ollama介绍二、安装Ollama 1、标准安装 2、国内加速三、升级Ollama版本四、使用Ollama 1、启动ollama服务 systemctl start ollama.service ollama serve 2、使用ollama命令 ollama run 运行模型 ollama ps 查看正在运行的模型 ollama list 查看(本地)…...

编程日记 2025/5/6 9:19:30

ubuntu/kali安装c-jwt-cracker

1.下载安装包可以去GitHub下载解压，我这直接在kali克隆下来了。（网络不好可能克隆不下来） git clone https://github.com/brendan-rius/c-jwt-cracker.git 2.如果下载的压缩包就需要进行解压，克隆的直接进入目录就好了。 unzi…...

编程日记 2025/5/6 23:03:53

MySql按年月日自动创建分区存储过程

-- 创建存储过程【通过数据库和表名】建立【partition_number】get分区，分区间隔为【gaps】 -- datasource 数据库名称 -- table_name 数据库表名 -- partition_number 新建分区的数量 -- partition_type 分区类型（0-按天分区，1-按月分区&…...

编程日记 2025/5/6 15:33:28

Spring配置文件中：密码明文改为密文处理方式（通用方法）

目录一、背景二、思路 A) 普通方式 B) 适合bootstrap.properties方式三、示例 A) 普通方式（连接Redis集群） A) 普通方式（连接RocketMQ） B) 适合bootstrap.properties方式四、总结一、背景 SpringBoot和Sprin…...

编程日记 2025/5/7 9:56:49

树的模拟实现

一.链式前向星所谓链式前向星，就是用链表的方式实现树。其中的链表是用数组模拟实现的链表。首先我们需要创建一个足够大的数组h，作为所有结点的哨兵位。创建两个足够大的数组e和ne，一个作为数据域，一个作为指针域。创建一个变…...

编程日记 2025/5/7 9:55:44

计算机图形学【直线和圆的生成算法】

在计算机图形学中，光栅化是将几何图元转换成一个光栅图像（像素或点）在屏幕上输出的过程。光栅化可实现图形变为二维图像，其目的是将连续的几何图形转换为离散的像素点。光栅化算法的基本原理包括两个主要步骤：首先&…...

编程日记 2025/5/7 4:12:47

OpenAI 故障复盘 - 阿里云容器服务与可观测产品如何保障大规模 K8s 集群稳定性

本文作者： 容器服务团队：刘佳旭、冯诗淳可观测团队：竺夏栋、麻嘉豪、隋吉智一、前言 Kubernetes(K8s)架构已经是当今 IT 架构的主流与事实标准（CNCF Survey[1]）。随着承接的业务规模越来越大，用户也在使…...

编程日记 2025/5/7 8:37:08

【深度学习】Pytorch：加载自定义数据集

本教程将使用 flower_photos 数据集演示如何在 PyTorch 中加载和导入自定义数据集。该数据集包含不同花种的图像，每种花的图像存储在以花名命名的子文件夹中。我们将深入讲解每个函数和对象的使用方法，使读者能够推广应用到其他数据集任务中。 flower_ph…...

编程日记 2025/5/7 10:46:28

vue js实现时钟以及刻度效果

2025.01.08今天我学习如何用js实现时钟样式，效果如下： 一、html代码如下： <template><div class"notice_border"><div class"notice_position notice_name_class" v-for"item in …...

编程日记 2025/5/5 20:20:21

js基础---注释与结束符

JavaScript 基础：注释与结束符注释注释是代码中用于解释说明的部分，不会被执行，主要有两种类型： 单行注释符号：//作用：从符号开始到该行末尾的所有内容都会被忽略，不会被执行。示例代码&…...

编程日记 2025/5/6 0:41:50

from pytorch3d import _C问题

离线安装pytorch3d后，先测试： import pytorch3d 没问题后，再测试： from pytorch3d import _C 单独测试会出现： ImportError: libc10.so: cannot open shared object file: No such file or directory 或者类似不…...

编程日记 2025/4/24 14:38:32

PHP进阶-在Ubuntu上搭建LAMP环境教程

本文将为您提供一个在Ubuntu服务器上搭建LAMP（Linux, Apache, MySQL, PHP）环境的完整指南。通过本文，您将学习如何安装和配置Apache、MySQL、PHP，并将您的PHP项目部署到服务器上。本文适用于Ubuntu 20.04及更高版本。一、系统更新…...

编程日记 2025/5/5 8:25:13

SQLite 命令

关于《SQLite 命令》的文章，我可以为您提供一个概要。SQLite是一个轻量级的嵌入式关系数据库管理系统，它以单个文件的形式存储数据，非常适合用于不需要传统数据库服务器的场景。SQLite3的命令行工具（sqlite3.exe）是一个…...

编程日记 2025/5/6 12:14:19

ASP.NET Core 实现微服务 - Consul 配置中心

这一次我们继续介绍微服务相关组件配置中心的使用方法。本来打算介绍下携程开源的重型配置中心框架 apollo 但是体系实在是太过于庞大，还是让我爱不起来。因为前面我们已经介绍了使用Consul 做为服务注册发现的组件 ，那么干脆继续使用 Consul 来作为配置…...

编程日记 2025/5/1 0:19:20

自定义Java注解及其应用

上一篇博客：Java注解写在前面：大家好！我是晴空๓。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：https://ac-fun.blog.csdn.net/。非常感谢大家的支持。…...

编程日记 2025/4/30 12:54:42

回归预测 | MATLAB实GRU多输入单输出回归预测

回归预测 | MATLAB实GRU多输入单输出回归预测目录回归预测 | MATLAB实GRU多输入单输出回归预测预测效果基本介绍程序设计参考资料预测效果基本介绍回归预测 | MATLAB实GRU多输入单输出回归预测。使用GRU作为RNN的一种变体来处理时间序列数据。GRU相比传统的RNN有较好的记…...

编程日记 2025/5/7 10:21:41

ISP流程--去马赛克详解

前言本期我们将深入讨论ISP流程中的去马赛克处理。我们熟知，彩色图像由一个个像元组成，每个像元又由红、绿、蓝（RGB）三通道构成。而相机传感器只能感知光的强度，无法直接感知光谱信息，即只有亮暗而没有颜色…...

编程日记 2025/5/1 20:35:39

用户注册模块用户校验（头条项目-05）

1 用户注册后端逻辑 1.1 接收参数 username request.POST.get(username) password request.POST.get(password) phone request.POST.get(phone) 1.2 校验参数前端校验过的后端也要校验，后端的校验和前端的校验是⼀致的 # 判断参数是否⻬全 # 判断⽤户名是否…...

编程日记 2025/5/4 23:04:44

【大数据】Apache Superset：可视化开源架构

Apache Superset是什么 Apache Superset 是一个开源的现代化数据可视化和数据探索平台，主要用于帮助用户以交互式的方式分析和展示数据。有不少丰富的可视化组件，可以将数据从多种数据源（如 SQL 数据库、数据仓库、NoSQL 数据库等&#xff0…...

编程日记 2025/5/7 1:50:05

如何搭建 Vue.js 开源项目的 CI/CD 流水线

网罗开发 （小红书、快手、视频号同名） 大家好，我是展菲，目前在上市企业从事人工智能项目研发管理工作，平时热衷于分享各种编程领域的软硬技能知识以及前沿技术，包括iOS、前端、Harmony OS、Java、Python等…...

编程日记 2025/5/5 18:03:30

OCR文字识别—基于PP-OCR模型实现ONNX C++推理部署

概述 PaddleOCR 是一款基于 PaddlePaddle 深度学习平台的开源 OCR 工具。PP-OCR是PaddleOCR自研的实用的超轻量OCR系统。它是一个两阶段的OCR系统，其中文本检测算法选用DB，文本识别算法选用CRNN，并在检测和识别模块之间添加文本方向分类器&a…...

编程日记 2025/4/30 20:02:17

国产3D CAD将逐步取代国外软件

在工业软件的关键领域，计算机辅助设计（CAD）软件对于制造业的重要性不言而喻。近年来，国产 CAD 的发展态势迅猛，展现出巨大的潜力与机遇，正逐步改变着 CAD 市场长期由国外软件主导的格局。国产CAD发展现状 …...

编程日记 2025/5/3 7:41:12

GoLand 如何集成 Netty？

目录 1.回答问题： 2.以下是实现类似 Netty 功能的步骤： 2.1 实现基本的网络通信功能： 3. 使用 Go 的第三方库实现 Netty 功能 4.实现类似 Netty 的事件循环： 5. 运用场景： 1.回答问题： 要在 GoLand 中…...

编程日记 2025/5/6 11:29:38

C++中为什么要把基类指针指向子类对象？

为什么要把基类指针指向子类对象？ 1）实现多态性动态绑定行为：通过基类指针指向子类对象，可以利用 C 的多态机制。当基类中有虚函数，并且子类重写了这些虚函数时，通过基类指针调用虚函数，实际调…...

编程日记 2025/5/5 10:42:58

2025年第三届“华数杯”国际赛A题解题思路与代码（Matlab版）

游泳竞技策略优化模型代码详解（MATLAB版） 第一题：速度优化模型本部分使用MATLAB实现游泳运动员在不同距离比赛中的速度分配策略优化。 1. 模型概述模型包含三个主要文件： speed_optimization.m: 核心优化类plot_speeds.m: …...

编程日记 2025/5/5 0:43:16

做一个简单的Django 《股票自选助手》显示用akshare 库（A股数据获取）

图： 股票自选助手这是一个基于 Django 开发的 A 股自选股票信息查看系统。系统使用 akshare 库获取实时股票数据，支持添加、删除和更新股票信息。功能特点支持添加自选股票实时显示股票价格和涨跌幅一键更新所有股票数据支持删除不需要的股票使用中…...

编程日记 2025/5/3 20:56:37

深入探索 ScottPlot.WPF：在 Windows 桌面应用中绘制精美图表的利器

一、ScottPlot.WPF 简介 ScottPlot.WPF 是基于 ScottPlot 绘图库专门为 Windows Presentation Foundation (WPF) 框架量身定制的强大绘图组件。它无缝集成到 WPF 应用程序中，为开发者提供了一种简洁、高效的方式来可视化数据，无论是科学研究中的实验数据展示、金融领域的行情…...

编程日记 2025/4/30 7:33:30

Spring bean的生命周期和扩展

接AnnotationConfigApplicationContext流程看实例化的beanPostProcessor-CSDN博客，以具体实例看bean生命周期的一些执行阶段 bean生命周期流程生命周期扩展处理说明实例化:createBeanInstance 构造方法， 如Autowired的构造方法注入依赖bean 如UserSer…...

编程日记 2025/5/4 5:11:28

【Docker】docker compose 安装 Redis Stack

注：整理不易，请不要吝啬你的赞和收藏。前文 Redis Stack 什么是？ 简单来说，Redis Stack 是增强版的 Redis ，它在传统的 Redis 数据库基础上增加了一些高级功能和模块，以支持更多的使用场景和需求。Redis…...

编程日记 2025/5/4 2:17:34

Life Long Learning（李宏毅）机器学习 2023 Spring HW14 (Boss Baseline)

1. 终身学习简介神经网络的典型应用场景是，我们有一个固定的数据集，在其上训练并获得模型参数，然后将模型应用于特定任务而无需进一步更改模型参数。然而，在许多实际工程应用中，常见的情况是系统可以不断地获取新数据，例如 Web 应用程序中的新用户数据或自动驾驶中的…...

编程日记 2025/4/26 23:40:15

JavaEE之线程池

前面我们了解了多个任务可以通过创建多个线程去处理，达到节约时间的效果，但是每一次的线程创建和销毁也是会消耗计算机资源的，那么我们是否可以将线程进阶一下，让消耗计算机的资源尽可能缩小呢？线程池可以达到此效果&a…...

编程日记 2025/5/3 22:03:35

贪心算法笔记

大概内容

例题讲解

相关文章：