备战蓝桥杯---数据结构与STL应用(入门4)
本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题
话不多说,直接看题:

下面为分析:
很显然,我们在整体上以s[i]为基准,先把士兵按s[i]排好。然后,我们先求s[i]大的开始,即规定选人数不超过s[i]的士兵,下面为图解:

下面为AC代码:
#include<bits/stdc++.h>
using namespace std;
struct node{long long v,s;
}a[1000100];
long long n;
bool cmp(node a,node b){return a.s>b.s;
}
signed main(){cin>>n;for(int i=1;i<=n;i++){scanf("%lld%lld",&a[i].v,&a[i].s);}sort(a+1,a+1+n,cmp);priority_queue<long long,vector<long long>,greater<long long> > q;long long cap=a[1].s,sum=a[1].v,max1=-1;q.push(a[1].v);for(int i=2;i<=n;i++){if(a[i].s==cap){q.push(a[i].v);sum+=a[i].v;if(q.size()>cap){sum-=q.top();q.pop();}} else{cap=a[i].s;q.push(a[i].v);sum+=a[i].v;while(q.size()>cap){sum-=q.top();q.pop();}}max1=max(max1,sum);}cout<<max1;
}
再来一道类似的:

下面为分析:
类似的,我们指定一个基准,我们按deadline升序排好,从小的开始枚举。
如果前面的时间加当前所需没超当前建筑的deadline,我们就添加。
否则,我们用它与前面所需时间max的比,如果比他小就替换。
下面为AC代码:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
struct node{int t1,t2;
}a[150010];
bool cmp(node a,node b){return a.t2<b.t2;}
signed main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d%d",&a[i].t1,&a[i].t2);sort(a+1,a+n+1,cmp);priority_queue<int> q;int dead=-1,cnt=0,sum=0;for(int i=1;i<=n;i++){q.push(a[i].t1);cnt++;sum+=a[i].t1;if(a[i].t2!=dead) dead=a[i].t2;if(sum>dead){sum-=q.top();cnt--;q.pop();} }cout<<cnt;
}
让我们总结一下,本专题围绕利用优先队列解决贪心选择上的“反悔”(或优化)问题(常用于固定枚举一个基准值)
最后,举个形象的例子:我们的成长就是从一开始的幼稚不断地经历岁月的打磨,见识的增长,不断优化,最终走向成熟。
希望可以和大家一起继续前行!
相关文章:
备战蓝桥杯---数据结构与STL应用(入门4)
本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题 话不多说,直接看题: 下面为分析: 很显然,我们在整体上以s[i]为基准,先把士兵按s[i]排好。然后,我们先求s[i]大的开始,即规定选人数…...
2023_12蓝桥杯STEMA 考试 Scratch 中级试卷解析
2023蓝桥杯STEMA 考试 Scratch 中级试卷(12 月)解析 由于没有原始文件,这里使用的角色和背景和实际题目会有所差异,已经尽量还原原题,以下代码仅供参考。吐槽一句:蓝桥杯越来越变态了!\(`Δ’)/\(`Δ’)/\(`Δ’)/孩子学习速度永远也赶不上内卷的速度。 一、选择…...
从编程中理解:大脑中的杏仁核
编程和神经科学在某种程度上可以相互借鉴,尤其是在模拟大脑功能时。让我们以Unity游戏引擎中的C#代码为例,结合金庸武侠小说中的人物形象来构建一个类比故事,探讨如何通过编程模拟大脑中杏仁核的作用。 假设在一款名为“脑海江湖”的Unity游戏中,主角张无忌(代指玩家角色…...
Maven dependency中的scope
Maven的一个哲学是惯例优于配置(Convention Over Configuration), Maven默认的依赖配置项中,scope的默认值是compile。 scope的分类 compile(默认) 含义: compile 是默认值,如果没有指定 scope 值,该元素…...
代码随想录算法训练营DAY11 | 栈与队列 (2)
一、LeetCode 20 有效的括号 题目链接:20.有效的括号https://leetcode.cn/problems/valid-parentheses/ 思路:遇到左括号直接进栈;遇到右括号判断站顶是否有匹配的括号,没有就返回flase,有就将栈顶元素出栈࿱…...
【Spring实战】33 Spring Boot3 集成 Nacos 配置中心
文章目录 1. 配置中心定义2. 解决哪些问题3. 常用的配置中心4. 使用示例1)没引入 Nacos 配置中心2)引入依赖3)配置Nacos连接信息4)在 Nacos 上配置属性5)在 Spring Boot 中使用配置6)启动服务&验证7&am…...
ElementUI安装与使用指南
Element官网-安装指南 提醒一下:下面实例讲解是在Mac系统演示的; 一、开发环境配置 电脑需要先安装好node.js和vue2或者vue3 安装Node.js Node.js 中文网 安装node.js命令:brew install node node.js安装完后,输入࿱…...
Opencv——图片卷积
图像滤波是尽量保留图像细节特征的条件下对目标图像的噪声进行抑制,是图像预处理中不可缺少的操作,其处理效果的好坏将直接影响到后续图像处理和分析的有效性和可靠性。 线性滤波是图像处理最基本的方法,它允许我们对图像进行处理,产生很多不同的效果。首先,我们需要一个二…...
项目安全-----加密算法实现
目录 对称加密算法 AES (ECB模式) AES(CBC 模式)。 非对称加密 对称加密算法 对称加密算法,是使用相同的密钥进行加密和解密。使用对称加密算法来加密双方的通信的话,双方需要先约定一个密钥,加密方才能加密&#…...
只用一台服务器部署上线(宝塔面板) 前后端+数据库
所需材料 工具:安装宝塔面板服务器至少一台、域名一个 前端:生成dist文件(前端运行build命令) 后端:生成jar包(maven运行package命令) 准备: 打开宝塔面板,点击进入软…...
《Pandas 简易速速上手小册》第8章:Pandas 高级数据分析技巧(2024 最新版)
文章目录 8.1 使用 apply 和 map 函数8.1.1 基础知识8.1.2 重点案例:客户数据清洗和转换8.1.3 拓展案例一:产品评分调整8.1.4 拓展案例二:地址格式化 8.2 性能优化技巧8.2.1 基础知识8.2.2 重点案例:大型销售数据分析8.2.3 拓展案…...
计算机网络_1.6.2 计算机网络体系结构分层的必要性
1.6.2 计算机网络体系结构分层的必要性 一、五层原理体系结构每层各自主要解决什么问题1、物理层2、数据链路层3、网络层4、运输层5、应用层 二、总结三、练习 笔记来源: B站 《深入浅出计算机网络》课程 本节主要介绍实现计算机网络需要解决哪些问题?以…...
跟着cherno手搓游戏引擎【18】抽象Shader、项目小修改
抽象: Shader.h: #pragma once #include <string>namespace YOTO {class Shader {public:virtual~Shader()default;virtual void Bind()const0;virtual void UnBind()const0;static Shader* Create(const std::string& vertexSrc, const std::string&am…...
每日OJ题_算法_模拟②_力扣495. 提莫攻击
目录 力扣495. 提莫攻击 解析代码 力扣495. 提莫攻击 495. 提莫攻击 难度 简单 在《英雄联盟》的世界中,有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希(编者注:寒冰射手)进入中毒状态。 当提莫攻击艾希,…...
freertos 源码分析二 list链表源码
list.c 一、链表初始化 void vListInitialise( List_t * const pxList ) { pxList->pxIndex ( ListItem_t * ) &…...
Peter算法小课堂—Dijkstra最短路算法
大家好,我们人见人爱、花见花开、车见车爆胎的Peter Pan来啦,hia~hia~hia。今天,我们今天来学习毒瘤的最短路算法啦。啊这……什么是Dijkstra算法?长文警告⚠ 正经点啊 手算样例 大家思考一下,你在手算样例的时候&am…...
Python 读取和写入包含中文的csv、xlsx、json文件
背景 最近在做数据的训练,经常需要读取写入csv、xlsx、json文件来获取数据,在这里做简单总结记录。 ps: 读取和写入中文文件时,需要确保文件的编码格式是正确的。通常情况使用UTF-8编码格式。如果使用其他编码格式可能会导致读取或写入时出…...
【算法】利用递归dfs解决二叉树算法题(C++)
文章目录 1. 前言2. 算法题2331.计算布尔二叉树的值129.求根节点到叶节点数字之和LCR047.二叉树剪枝98.验证二叉搜索树230.二叉搜索树中第K小的元素257.二叉树的所有路径 1. 前言 有关 递归 的相关解释与解题 请看下文: 以汉诺塔理解递归、并用递归解决算法题 对于…...
计算机网络_1.6.1 常见的三种计算机网络体系结构
1.6.1 常见的三种计算机网络体系结构 1、OSI(七层协议)标准失败的原因2、TCP/IP参考模型3、三种网络体系结构对比 笔记来源: B站 《深入浅出计算机网络》课程 1、OSI(七层协议)标准失败的原因 (1…...
XML传参方式
export function groupLoginAPI(xmlData) {return http.post(/tis/group/1.0/login, xmlData, {headers: {Content-Type: application/xml,X-Requested-With: AAServer/4.0,}}) }import {groupLoginAPI} from "../api/user"; function (e) { //xml格式传参let groupX…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
第 86 场周赛:矩阵中的幻方、钥匙和房间、将数组拆分成斐波那契序列、猜猜这个单词
Q1、[中等] 矩阵中的幻方 1、题目描述 3 x 3 的幻方是一个填充有 从 1 到 9 的不同数字的 3 x 3 矩阵,其中每行,每列以及两条对角线上的各数之和都相等。 给定一个由整数组成的row x col 的 grid,其中有多少个 3 3 的 “幻方” 子矩阵&am…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
JDK 17 序列化是怎么回事
如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
