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

备战蓝桥杯---数据结构与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)

本专题主要是关于利用优先队列解决贪心选择上的“反悔”问题 话不多说&#xff0c;直接看题&#xff1a; 下面为分析&#xff1a; 很显然&#xff0c;我们在整体上以s[i]为基准&#xff0c;先把士兵按s[i]排好。然后&#xff0c;我们先求s[i]大的开始&#xff0c;即规定选人数…...

2023_12蓝桥杯STEMA 考试 Scratch 中级试卷解析

2023蓝桥杯STEMA 考试 Scratch 中级试卷(12 月)解析 由于没有原始文件,这里使用的角色和背景和实际题目会有所差异,已经尽量还原原题,以下代码仅供参考。吐槽一句:蓝桥杯越来越变态了!\(`Δ’)/\(`Δ’)/\(`Δ’)/孩子学习速度永远也赶不上内卷的速度。 一、选择…...

从编程中理解:大脑中的杏仁核

编程和神经科学在某种程度上可以相互借鉴,尤其是在模拟大脑功能时。让我们以Unity游戏引擎中的C#代码为例,结合金庸武侠小说中的人物形象来构建一个类比故事,探讨如何通过编程模拟大脑中杏仁核的作用。 假设在一款名为“脑海江湖”的Unity游戏中,主角张无忌(代指玩家角色…...

Maven dependency中的scope

Maven的一个哲学是惯例优于配置(Convention Over Configuration), Maven默认的依赖配置项中&#xff0c;scope的默认值是compile。 scope的分类 compile&#xff08;默认&#xff09; 含义&#xff1a; compile 是默认值&#xff0c;如果没有指定 scope 值&#xff0c;该元素…...

代码随想录算法训练营DAY11 | 栈与队列 (2)

一、LeetCode 20 有效的括号 题目链接&#xff1a;20.有效的括号https://leetcode.cn/problems/valid-parentheses/ 思路&#xff1a;遇到左括号直接进栈&#xff1b;遇到右括号判断站顶是否有匹配的括号&#xff0c;没有就返回flase&#xff0c;有就将栈顶元素出栈&#xff1…...

【Spring实战】33 Spring Boot3 集成 Nacos 配置中心

文章目录 1. 配置中心定义2. 解决哪些问题3. 常用的配置中心4. 使用示例1&#xff09;没引入 Nacos 配置中心2&#xff09;引入依赖3&#xff09;配置Nacos连接信息4&#xff09;在 Nacos 上配置属性5&#xff09;在 Spring Boot 中使用配置6&#xff09;启动服务&验证7&am…...

ElementUI安装与使用指南

Element官网-安装指南 提醒一下&#xff1a;下面实例讲解是在Mac系统演示的&#xff1b; 一、开发环境配置 电脑需要先安装好node.js和vue2或者vue3 安装Node.js Node.js 中文网 安装node.js命令&#xff1a;brew install node node.js安装完后&#xff0c;输入&#xff1…...

Opencv——图片卷积

图像滤波是尽量保留图像细节特征的条件下对目标图像的噪声进行抑制,是图像预处理中不可缺少的操作,其处理效果的好坏将直接影响到后续图像处理和分析的有效性和可靠性。 线性滤波是图像处理最基本的方法,它允许我们对图像进行处理,产生很多不同的效果。首先,我们需要一个二…...

项目安全-----加密算法实现

目录 对称加密算法 AES &#xff08;ECB模式&#xff09; AES(CBC 模式)。 非对称加密 对称加密算法 对称加密算法&#xff0c;是使用相同的密钥进行加密和解密。使用对称加密算法来加密双方的通信的话&#xff0c;双方需要先约定一个密钥&#xff0c;加密方才能加密&#…...

只用一台服务器部署上线(宝塔面板) 前后端+数据库

所需材料 工具&#xff1a;安装宝塔面板服务器至少一台、域名一个 前端&#xff1a;生成dist文件&#xff08;前端运行build命令&#xff09; 后端&#xff1a;生成jar包&#xff08;maven运行package命令&#xff09; 准备&#xff1a; 打开宝塔面板&#xff0c;点击进入软…...

《Pandas 简易速速上手小册》第8章:Pandas 高级数据分析技巧(2024 最新版)

文章目录 8.1 使用 apply 和 map 函数8.1.1 基础知识8.1.2 重点案例&#xff1a;客户数据清洗和转换8.1.3 拓展案例一&#xff1a;产品评分调整8.1.4 拓展案例二&#xff1a;地址格式化 8.2 性能优化技巧8.2.1 基础知识8.2.2 重点案例&#xff1a;大型销售数据分析8.2.3 拓展案…...

计算机网络_1.6.2 计算机网络体系结构分层的必要性

1.6.2 计算机网络体系结构分层的必要性 一、五层原理体系结构每层各自主要解决什么问题1、物理层2、数据链路层3、网络层4、运输层5、应用层 二、总结三、练习 笔记来源&#xff1a; B站 《深入浅出计算机网络》课程 本节主要介绍实现计算机网络需要解决哪些问题&#xff1f;以…...

跟着cherno手搓游戏引擎【18】抽象Shader、项目小修改

抽象&#xff1a; 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. 提莫攻击 难度 简单 在《英雄联盟》的世界中&#xff0c;有一个叫 “提莫” 的英雄。他的攻击可以让敌方英雄艾希&#xff08;编者注&#xff1a;寒冰射手&#xff09;进入中毒状态。 当提莫攻击艾希&#xff0c…...

freertos 源码分析二 list链表源码

list.c 一、链表初始化 void vListInitialise( List_t * const pxList ) { pxList->pxIndex ( ListItem_t * ) &…...

Peter算法小课堂—Dijkstra最短路算法

大家好&#xff0c;我们人见人爱、花见花开、车见车爆胎的Peter Pan来啦&#xff0c;hia~hia~hia。今天&#xff0c;我们今天来学习毒瘤的最短路算法啦。啊这……什么是Dijkstra算法&#xff1f;长文警告⚠ 正经点啊 手算样例 大家思考一下&#xff0c;你在手算样例的时候&am…...

Python 读取和写入包含中文的csv、xlsx、json文件

背景 最近在做数据的训练&#xff0c;经常需要读取写入csv、xlsx、json文件来获取数据&#xff0c;在这里做简单总结记录。 ps: 读取和写入中文文件时&#xff0c;需要确保文件的编码格式是正确的。通常情况使用UTF-8编码格式。如果使用其他编码格式可能会导致读取或写入时出…...

【算法】利用递归dfs解决二叉树算法题(C++)

文章目录 1. 前言2. 算法题2331.计算布尔二叉树的值129.求根节点到叶节点数字之和LCR047.二叉树剪枝98.验证二叉搜索树230.二叉搜索树中第K小的元素257.二叉树的所有路径 1. 前言 有关 递归 的相关解释与解题 请看下文&#xff1a; 以汉诺塔理解递归、并用递归解决算法题 对于…...

计算机网络_1.6.1 常见的三种计算机网络体系结构

1.6.1 常见的三种计算机网络体系结构 1、OSI&#xff08;七层协议&#xff09;标准失败的原因2、TCP/IP参考模型3、三种网络体系结构对比 笔记来源&#xff1a; B站 《深入浅出计算机网络》课程 1、OSI&#xff08;七层协议&#xff09;标准失败的原因 &#xff08;1&#xf…...

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…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

线程与协程

1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指&#xff1a;像函数调用/返回一样轻量地完成任务切换。 举例说明&#xff1a; 当你在程序中写一个函数调用&#xff1a; funcA() 然后 funcA 执行完后返回&…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...