【算法】反悔贪心
文章目录
- 反悔贪心
- 力扣题目列表
- 630. 课程表 III
- 871. 最低加油次数
- LCP 30. 魔塔游戏
- 2813. 子序列最大优雅度
- 洛谷题目列表
- P2949 [USACO09OPEN] Work Scheduling G
- P1209 [USACO1.3] 修理牛棚 Barn Repair
- P2123 皇后游戏(🚹省选/NOI− TODO)
- 相关链接
反悔贪心
思路是无论当前的选项是否最优都接受,然后进行比较,如果选择之后不是最优了,则反悔,舍弃掉这个选项;否则,正式接受。如此往复。
力扣题目列表
630. 课程表 III
https://leetcode.cn/problems/course-schedule-iii/description/?envType=daily-question&envId=2023-09-11
提示:
1 <= courses.length <= 104
1 <= durationi, lastDayi <= 104
解法看注释就很清楚了。
class Solution {public int scheduleCourse(int[][] courses) {// 按照截止时间从小到大排序Arrays.sort(courses, (a, b) -> a[1] - b[1]);// 最大堆PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);int day = 0; // 记录当前使用了多少天for (int[] c: courses) {int d = c[0], t = c[1];if (day + d <= t) {// 如果可以学,直接学day += d;pq.offer(d);} else if (!pq.isEmpty() && pq.peek() > d) {// 如果不可以学,检查已经选了的课程中有没有耗时更长的替换掉day -= pq.poll() - d;pq.offer(d);}}// 最后的答案就是队列中已选课程的数量return pq.size();}
}
871. 最低加油次数
https://leetcode.cn/problems/minimum-number-of-refueling-stops/
提示:
1 <= target, startFuel <= 10^9
0 <= stations.length <= 500
1 <= positioni < positioni+1 < target
1 <= fueli < 10^9
按照加油站的出现顺序排序。
用堆维护目前可以加的油,每次路过一个加油站先不加而是放入优先队列中,等到走不动了再一个个从大到小加油。
class Solution {public int minRefuelStops(int target, int startFuel, int[][] stations) {// 按照出现顺序排序Arrays.sort(stations, (a, b) -> a[0] - b[0]);PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);int ans = 0, pos = startFuel;for (int[] s: stations) {if (pos >= target) return ans;int p = s[0], f = s[1];while (pos < p && !pq.isEmpty()) {pos += pq.poll();ans++;}if (pos < p) return -1;else pq.offer(f);}while (pos < target && !pq.isEmpty()) {pos += pq.poll();ans++;}return pos < target? -1: ans;}
}
LCP 30. 魔塔游戏
https://leetcode.cn/problems/p0NxJO/
提示:
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
先检查是否可以访问完全部房间,如果不可以直接返回-1。
如果不可以,每次遇到负数先放入优先队列中去,当血量不够时,再依次从小到大取出堆中的负数调换到队尾。
class Solution {public int magicTower(int[] nums) {if (Arrays.stream(nums).sum() < 0) return -1;int ans = 0;// pq中存放目前遇到的负数PriorityQueue<Integer> pq = new PriorityQueue<>();long s = 1;for (int x: nums) {s += x;if (x < 0) pq.offer(x);while (s <= 0) {// 每次把最小的移动到最后面去s -= pq.poll();ans++;}}return ans;}
}
2813. 子序列最大优雅度
https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/description/
提示:
1 <= items.length == n <= 10^5
items[i].length == 2
items[i][0] == profiti
items[i][1] == categoryi
1 <= profiti <= 10^9
1 <= categoryi <= n
1 <= k <= n
按照利润从大到小排序。
i < k 时直接加入,如果有重复的类别就将当前元素放入栈中(因为是从大到小枚举,所以栈顶一定是利润最小的)
当 i > k 时,如果当前元素还没有出现过,就可以尝试替换掉重复类型中利润最小的元素。
class Solution {public long findMaximumElegance(int[][] items, int k) {// 按利润从大到小排序Arrays.sort(items, (a, b) -> b[0] - a[0]);long ans = 0, totalProfit = 0;Set<Integer> s = new HashSet<>();Deque<Integer> stk = new ArrayDeque<>();for (int i = 0; i < items.length; ++i) {int p = items[i][0], c = items[i][1];if (i < k) {totalProfit += p;if (s.contains(c)) stk.push(p);s.add(c);} else if (!stk.isEmpty() && !s.contains(c)) {totalProfit -= stk.pop() - p;s.add(c);}ans = Math.max(ans, totalProfit + (long)s.size() * s.size());}return ans;}
}
注意代码中的 s.add(c);
不能提出 if-else 之外,否则会影响答案。
洛谷题目列表
P2949 [USACO09OPEN] Work Scheduling G
https://www.luogu.com.cn/problem/P2949
import java.util.*;class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[][] g = new int[n][2];for (int i = 0; i < n; ++i) {g[i][0] = sc.nextInt();g[i][1] = sc.nextInt();}// 按照截止时间从小到大排序Arrays.sort(g, (a, b) -> a[0] - b[0]);long ans = 0;PriorityQueue<Integer> pq = new PriorityQueue<>();for (int[] p: g) {// 如果当前工作不超时 加入答案和优先队列中if (pq.size() < p[0]) {pq.offer(p[1]);ans += p[1];} else if (!pq.isEmpty() && p[1] > pq.peek()) {// 当前工作超时 和已经选了的工作中最小的交换ans += p[1] - pq.poll();pq.offer(p[1]);}}System.out.println(ans);}
}
P1209 [USACO1.3] 修理牛棚 Barn Repair
https://www.luogu.com.cn/problem/P1209
记得要对输入数据排序!
import java.io.BufferedInputStream;
import java.lang.reflect.Array;
import java.util.*;public class Main {public static void main(String[] args) {Scanner sin = new Scanner(new BufferedInputStream(System.in));int m = sin.nextInt(), s = sin.nextInt(), c = sin.nextInt();PriorityQueue<Long> pq = new PriorityQueue<>();int[] a = new int[c];long last = -1, ans = c;m--;for (int i = 0; i < c; ++i) {a[i] = sin.nextInt();}Arrays.sort(a);for (int i = 0; i < c; ++i) {int p = a[i];if (last != -1 && last < p - 1) {pq.add(p - last - 1);m--;}last = p;}while (m < 0 && !pq.isEmpty()) {m++;ans += pq.poll();}System.out.println(ans);}
}
每次将空格记录在优先队列中,当木板数量不够时,从小到大取出优先队列中的空格依次填上。
P2123 皇后游戏(🚹省选/NOI− TODO)
https://www.luogu.com.cn/problem/P2123
在这里插入代码片
相关链接
【力扣周赛】第 357 场周赛(⭐反悔贪心)
相关文章:

【算法】反悔贪心
文章目录 反悔贪心力扣题目列表630. 课程表 III871. 最低加油次数LCP 30. 魔塔游戏2813. 子序列最大优雅度 洛谷题目列表P2949 [USACO09OPEN] Work Scheduling GP1209 [USACO1.3] 修理牛棚 Barn RepairP2123 皇后游戏(🚹省选/NOI− TODO) 相关…...

Hadoop的安装和使用,Windows使用shell命令简单操作HDFS
1,Hadoop简介 Hadoop是一个能够对大量数据进行分布式处理的软件框架,并且是以一种可靠、高效、可伸缩的方式进行处理的,它具有以下几个方面的特性。 高可靠性。 高效性。 高可扩展性。 高容错性。 成本低。 运行在Linux平台上。 支持多种编程…...

ubuntu上ffmpeg使用framebuffer显示video
这个主题是想验证使用fbdev(Linux framebuffer device),将video直接显示到Linux framebuffer上,在FFmpeg中对应的FFOutputFormat 就是ff_fbdev_muxer。 const FFOutputFormat ff_fbdev_muxer {.p.name "fbdev",.p.long_…...

82 # koa-bodyparser 中间件的使用以及实现
准备工作 安装依赖 npm init -y npm i koakoa 文档:https://koajs.cn/# koa 中不能用回调的方式来实现,因为 async 函数执行的时候不会等待回调完成 app.use(async (ctx, next) > {console.log(ctx.path, ctx.method);if (ctx.path "/login…...

计算一串输出数字的累加和
计算一个文件内数字的累加和 awk {sum$1}END{print sum} 直接抽取数据以后的打印是这样的 cat step-iostat.1125.log |grep sda |cut -c "49-56" |awk {sum$1}END{print sum}...
python包导入原理解析
原文链接: https://www.cnblogs.com/hi3254014978/p/15317976.html 根据编程经验的不同,我们在运行程序时可能经常或者偶尔碰到下面这些问题,仔细观察后会发现这些问题无一例外都出现了一个相同的短语,很容易就可以发现࿰…...

MNIST手写数字辨识-cnn网路 (机器学习中的hello world,加油)
用PyTorch实现MNIST手写数字识别(非常详细) - 知乎 (zhihu.com) 参考来源(这篇文章非常适合入门来看,每个细节都讲解得很到位) 一、模块函数用法-查漏补缺: 1.关于torch.nn.functional.max_pool2d()的用法: 上述示例…...

论文笔记《3D Gaussian Splatting for Real-Time Radiance Field Rendering》
项目地址 原论文 Abstract 最近辐射场方法彻底改变了多图/视频场景捕获的新视角合成。然而取得高视觉质量仍需神经网络花费大量时间训练和渲染,同时最近较快的方法都无可避免地以质量为代价。对于无边界的完整场景(而不是孤立的对象)和 10…...
数据库管理系统,数据库,sql的基本介绍以及它们之间的关系
数据库管理系统(Database Management System,简称DBMS)是一种软件工具或系统,用于管理和维护数据库的创建、访问、更新和管理。DBMS允许用户在数据库中存储、检索和操作数据,同时提供了数据安全性、完整性和一致性的控…...
【Flowable】Springboot使用Flowable(一)
一、项目依赖 <dependency><groupId>org.flowable</groupId><artifactId>flowable-engine</artifactId><version>6.3.0</version></dependency><dependency><groupId>mysql</groupId><artifactId>my…...

戳泡泡小游戏
欢迎来到程序小院 戳泡泡 玩法: 鼠标点击上升的起泡泡,点击暴躁记录分数,不要让泡泡越过屏幕,共有三次复活生命,会有随机星星出现,点击即可暴躁全屏哦^^。开始游戏https://www.ormcc.com/play/gameStart/1…...

Redis缓存
1. Redis缓存相关问题 1.1 缓存穿透 缓存穿透是指查询一个数据库一定不存在的数据。 我们以前正常的使用Redis缓存的流程大致是: 1、数据查询首先进行缓存查询 2、如果数据存在则直接返回缓存数据 3、如果数据不存在,就对数据库进行查询࿰…...
mysql 插入更新数据
insert into insert into 语句进行插入时,如果插入的字段包含 主键或者唯一索引字段,那么, 1)主键或唯一索引 已存在,则插入失败 1062 - Duplicate entry 1 for key PRIMARY 2)只有主键或者唯一索 引不存…...

系统架构设计高级技能 · 软件产品线
现在的一切都是为将来的梦想编织翅膀,让梦想在现实中展翅高飞。 Now everything is for the future of dream weaving wings, let the dream fly in reality. 点击进入系列文章目录 系统架构设计高级技能 软件产品线 一、产品线概述二、产品线的过程模型2.1 双生命…...

C语言学习系列-->字符函数和字符串函数
文章目录 一、字符函数1、字符分类函数2、字符转换函数 二、字符串函数1、strlen概述模拟实现 2、strcpy概述模拟实现 3、strcat概述模拟实现 3、strcmp概述模拟实现 4、有限制的字符串函数strncpystrncatstrncmp 4、strstr概述模拟实现 一、字符函数 1、字符分类函数 包含头…...

尖端AR技术如何在美国革新外科手术实践?
AR智能眼镜已成为一种革新性的工具,在外科领域具有无穷的优势和无限的机遇。Vuzix与众多医疗创新企业建立了长期合作关系,如Pixee Medical、Medacta、Ohana One、Rods & Cones、Proximie等。这些公司一致认为Vuzix智能眼镜可有效提升手术实践&#x…...
【木板】Python实现-附ChatGPT解析
1.题目 木板 时间限制:1s 空间限制:256MB 限定语言:不限题目描述: 小明有n块木板,第i (1<=i<=n) 块木板的长度为ai.小明买了一块长度为m的木料,这块木料可以切割成任意块,拼接到已有的木板上用来加长木板。 小明想让最短的木板尽量长。 请问小明加长木板后,最短木板…...

第一章:绪论
1.1 系统架构概述 架构是体现在组件中的一个系统的基本组织、它们彼此的关系与环境的关系以及指导它的设计和发展的原则。 系统是组织起来完成某一特定功能火一组功能的组件集。系统这个术语包括了单独的应用程序、传统意义上的系统、子系统、系统之系统、产品线、整个企业及…...
C++面试知识点总结
知识点总结 <<符号表示该语句将把这个字符串发送给cout;该符号指出了信息流动的路径;cout的对象属性包括一个插入运算符(<<),它可以将其右侧的信息插入到流中,endl:重起一行。在输出流中插入en…...

从智能手机到智能机器人:小米品牌的高端化之路
原创 | 文 BFT机器人 前言 在前阵子落幕的2023世界机器人大会“合作之夜”上,北京经济技术开发区管委会完成了与世界机器人合作组织、小米机器人等16个重点项目签约,推动机器人创新链和产业链融合,其中小米的投资额达到20亿! 据了…...

龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?
现有的 Redis 分布式锁库(如 Redisson)相比于开发者自己基于 Redis 命令(如 SETNX, EXPIRE, DEL)手动实现分布式锁,提供了巨大的便利性和健壮性。主要体现在以下几个方面: 原子性保证 (Atomicity)ÿ…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成
一个面向 Java 开发者的 Sring-Ai 示例工程项目,该项目是一个 Spring AI 快速入门的样例工程项目,旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计,每个模块都专注于特定的功能领域,便于学习和…...
深度剖析 DeepSeek 开源模型部署与应用:策略、权衡与未来走向
在人工智能技术呈指数级发展的当下,大模型已然成为推动各行业变革的核心驱动力。DeepSeek 开源模型以其卓越的性能和灵活的开源特性,吸引了众多企业与开发者的目光。如何高效且合理地部署与运用 DeepSeek 模型,成为释放其巨大潜力的关键所在&…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...