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

让我们总结一下,本专题围绕利用优先队列解决贪心选择上的“反悔”(或优化)问题(常用于固定枚举一个基准值)

最后,举个形象的例子:我们的成长就是从一开始的幼稚不断地经历岁月的打磨,见识的增长,不断优化,最终走向成熟。

希望可以和大家一起继续前行!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/249042.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Neo4j介绍

1.Neo4j概述 Neo4j是一个开源的 无Shcema的 基于java开发的 图形数据库&#xff0c;它将结构化数据存储在图中而不是表中。它是一个嵌入式的、基于磁盘的、具备完全的事务特性的Java持久化引擎。程序数据是在一个面向对象的、灵活的网络结构下&#xff0c;而不是严格、静态的表…

计算机网络-物理层设备(中继器 集线器)

文章目录 中继器中继器的功能再生数字信号和再生模拟信号同一个协议 集线器&#xff08;多口中继器&#xff09;不具备定向传输的原因集线器是共享式设备的原因集线器的所有接口都处于同一个碰撞域&#xff08;冲突域&#xff09;内的原因 小结 中继器 中继器的功能 中继器的…

Qt 5.9.4 转 Qt 6.6.1 遇到的问题总结(三)

1.QSet: toList 中的toList 函数已不存在&#xff0c;遇到xx->toList改成直接用&#xff0c;如下&#xff1a; 2.开源QWT 图形库中QwtDial中的 setPenWidth 变成 setPenWidthF函数。 3.QDateTime 中无setTime_t 改为了setSecsSinceEpoch函数。 4.QRegExp 类已不存在 可以用Q…

给定n个结点的树,u,v两个结点可以配对当且仅当u不是v的祖先且v不是u的祖先,每个结点最多与一个结点配对,求最大配对个数

题目 思路: #include <bits/stdc++.h> using namespace std; #define int long long typedef long long ll; #define pb push_back #define lson p << 1 #define rson p << 1 | 1 #define fi first #define se second const int maxn = 1e6 + 5, maxm = 5e…

免费的ChatGPT网站(7个)

还在为找免费的chatGPT网站或者应用而烦恼吗&#xff1f;博主归纳总结了7个国内非常好用&#xff0c;而且免费的chatGPT网站&#xff0c;AI语言大模型&#xff0c;我们都来接触一下吧。 免费&#xff01;免费&#xff01;免费&#xff01;...&#xff0c;建议收藏保存。 1&…

简单高效 Learn LaTeX 013 - LaTex FloatingBody Tables (44 mins) 浮动体表格

浮动体是LaTex中的一个重要概念&#xff0c;这个视频演示了以浮动体为载体的表格的排版应用。 https://www.douyin.com/user/self?modal_id7305874487138913574&showTabpost

基于 LLM+LlamaIndex+NebulaGraph,构建大模型知识图谱的检索(RAG)方法

最近&#xff0c;围绕着利用 LLM&#xff08;Language Model&#xff09;和知识图谱&#xff08;KG&#xff0c;Knowledge Graphs&#xff09;构建RAG&#xff08;Retrieval Augmented Generation&#xff09;流程引起了很多关注。 在本文中&#xff0c;让我们通过利用 LlamaI…

鸿蒙会取代Android吗?听风就是雨

现在说取代还谈不上&#xff0c;毕竟这需要时间。安卓作为全球第一的手机操作系统&#xff0c;短时间内还无法取代。持平iOS甚至超过iOS有很大可能&#xff0c;最终会呈现“三足鼎立”有望超过安卓基数。 作为全新的鸿蒙操作系统&#xff0c;其现在已经是全栈自研底座。按照鸿…

(Sping Xml方式整合第三方框架)学习Spring的第十天

Spring整合mybatis 1 . 导入Mybatis整合Spring的相关坐标 <dependency><groupId>org.springframework</groupId><artifactId>spring-jdbc</artifactId><version>5.2.13.RELEASE</version></dependency><dependency><…

【20240131】USB相机(查看设备列表、打开设备)

USB相机采集 1、v4l2查看设备列表2、查看具体设备信息3、在桌面打开USB相机 1、v4l2查看设备列表 打开终端&#xff0c;输入&#xff1a;v4l2-ctl --list-devices usb设备在Webcam: Webcam栏&#xff0c;分别是video9和video10&#xff0c;下一步&#xff1a;确定哪一个是接入…

centos7 arm服务器编译安装gcc 9.2

前言 当前电脑的gcc版本为4.8.5,但是在编译其他依赖包的时候,出现各种奇怪的问题,会莫名其妙的中断编译。本地文章讲解如何自编译安装gcc,替换系统自带的gcc。 环境准备 下载缺失依赖库: yum install flex* 否则会报如下错误: gcc 9.2源码:下载地址 开始编译 1、解压…

pve宿主机更改网络导致没网,pve更改ip

一、问题描述 快过年了&#xff0c;我把那台一直在用的小型服务器&#xff0c;带回去了&#xff0c;导致网络发生了变更&#xff0c;需要对网络进行调整&#xff0c;否则连不上网&#xff0c;我这里改的是宿主机&#xff0c;不是pve虚拟机中的系统。 二、解决方法 pve用的是…

Django模型(七)

一、聚合与分组查询 1.1、准备数据 class Cook(models.Model):"""厨师"""name = models.CharField(max_length=32,verbose_name=厨师名)level = models.IntegerField(verbose_name=厨艺等级)age = models.IntegerField(verbose_name=年龄)sect …

【Docker】【深度学习算法】在Docker中使用gunicorn启动多个并行算法服务,优化算法服务:从单进程到并行化

文章目录 优化算法服务&#xff1a;从单进程到并行化单个服务架构多并行服务架构Docker化并指定并行服务数量 扩展知识 优化算法服务&#xff1a;从单进程到并行化 在实际应用中&#xff0c;单个算法服务的并发能力可能无法满足需求。为了提高性能和并发处理能力&#xff0c;我…

1.31学习总结

1.31 1.线段树 2.Bad Hair Day S&#xff08;单调栈&#xff09; 3.01迷宫(BFS连通块问题剪枝)&#xff08;连通性问题的并查集解法&#xff09; 4.健康的荷斯坦奶牛 Healthy Holsteins&#xff08;DFS&#xff09; 线段树与树状数组 线段树和树状数组的功能相似&#xff0c;但…

政安晨的机器学习笔记——跟着演练快速理解TensorFlow(适合新手入门)

准备工作 本笔记是假设您已经安装了Windows系统或Ubuntu系统的Anaconda&#xff08;或 Miniconda&#xff09;、Jupyter Notebook、TensorFLow&#xff0c;稍微了解Python语言&#xff0c;并可以进行一点点操作的基础上进行的。 如果您还不具备这个条件&#xff0c;去…

java 图书管理系统 spring boot项目

java 图书管理系统ssm框架 spring boot项目 功能有管理员模块&#xff1a;图书管理&#xff0c;读者管理&#xff0c;借阅管理&#xff0c;登录&#xff0c;修改密码 读者端&#xff1a;可查看图书信息&#xff0c;借阅记录&#xff0c;登录&#xff0c;修改密码 技术&#…

基于OpenCV的高压电力检测项目案例

一、项目背景与目标 随着高压电力设施的日益增多&#xff0c;传统的巡检方式已无法满足现代电力系统的需求。为此&#xff0c;我们决定利用计算机视觉技术&#xff0c;特别是OpenCV库&#xff0c;开发一个高压电力检测系统。目标是实现自动化、高精度的电力设备检测&#xff0c…

C#常见内存泄漏

背景 在开发中由于对语言特性不了解或经验不足或疏忽&#xff0c;往往会造成一些低级bug。而内存泄漏就是最常见的一个&#xff0c;这个问题在测试过程中&#xff0c;因为操作频次低&#xff0c;而不能完全被暴露出来&#xff1b;而在正式使用时&#xff0c;由于使用次数增加&…

AI学习(4): PyTorch实战-手写数字识别

1.介绍 在之前的文章中介绍了PyTorch的环境安装&#xff0c;和张量(tensor)的基本使用&#xff0c;为防止陷入枯燥的理论学习中&#xff0c;在这篇文章&#xff0c;我们将进行项目实战学习&#xff0c;项目主要内容: 基于MNIST数据集&#xff0c;实现一个手写数字识别的神经网…