lanqiaoOJ 3744:小蓝的智慧拼图购物 ← pair+优先队列
【题目来源】
https://www.lanqiao.cn/problems/3744/learning/
【题目描述】
在小蓝的生日那天,他得到了一个由神秘人赠送的拼图游戏,每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图,但他希望能尽可能地节省花费。小蓝手中有 N 个拼图,每个拼图的价格不同,第 i 个拼图的价格为 Pi。同时,他有 M 张优惠券,每张优惠券都有其特定的使用条件:只有当拼图的价格至少为 Li 时,他才能使用这张优惠券,并且可以享受 Di 的折扣。每张优惠券只能使用一次,且同一件拼图不能同时使用多张优惠券。如果某件拼图没有使用优惠券,则需要按照其标价购买。请你帮助小蓝计算出购买所有拼图所需的最少金额。
【输入格式】
第一行输入两个整数 N 和 M,分别表示拼图的数量和优惠券的数量。
接下来一行读入 N 个整数 P1,P2,…,Pn,表示每个拼图的价格。
接下来一行读入 M 个整数 L1,L2,…,Lm,表示每个优惠卷的使用门槛。
接下来一行读入 M 个整数 D1,D2,…,Dm,表示每个优惠卷的折扣。
数据范围保证:1≤N, M≤2×10^5,1≤Pi≤10^9,1≤Di≤Li≤10^9。
【输出格式】
输出一个整数,表示购买所有拼图所需的最少金额。
【输入样例】
2 5
12 8
5 11 5 11 10
3 9 1 3 2
【输出样例】
8
【算法分析】
● 注意“同一件拼图不能同时使用多张优惠券”,也要明确“优惠券使用后就不存在了”。
● 本题使用大根堆:priority_queue<int,vector<int>,less<int>> pq;
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=2e5+5;
int p[maxn];
pair<int,int> tkt[maxn];
priority_queue<int,vector<int>,less<int>> pq;
long long ans=0;int main() {int n,m;cin>>n>>m;for(int i=0; i<n; i++) cin>>p[i];for(int i=0; i<m; i++) cin>>tkt[i].first;for(int i=0; i<m; i++) cin>>tkt[i].second;sort(p,p+n); //small to bigsort(tkt,tkt+m); //small to bigint cnt=0;for(int i=0; i<n; i++) {while(p[i]>=tkt[cnt].first && cnt<m) {pq.push(tkt[cnt].second);cnt++;}if(!pq.empty()) {ans+=p[i]-pq.top();pq.pop();} else ans+=p[i];}cout << ans;return 0;
}/*
in1:
2 5
12 8
5 11 5 11 10
3 9 1 3 2out1:
8
------------
in2:
1 2
9
10 9
10 3out2:
6
*/
【参考文献】
https://www.lanqiao.cn/problems/3744/learning/
相关文章:
lanqiaoOJ 3744:小蓝的智慧拼图购物 ← pair+优先队列
【题目来源】https://www.lanqiao.cn/problems/3744/learning/【题目描述】 在小蓝的生日那天,他得到了一个由神秘人赠送的拼图游戏,每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图,但他希望能尽可能地节省花费。小蓝手中…...
Spring Boot教程之二十一:文件处理
Spring Boot – 文件处理 Spring Boot 是一种流行的、基于 Spring 的开源框架,用于开发强大的 Web 应用程序和微服务。由于它建立在 Spring 框架之上,因此它不仅具有 Spring 的所有功能,而且还包括某些特殊功能,例如自动配置、健康…...
【Linux】Linux的基本常识+指令
目录 1. 整体学习思维导图 2. 常见快捷键操作 3. 基本指令 pwd指令 whoami指令 ls 指令 touch指令 cd 指令 Stat 指令 mkdir 指令 alias指令 nano 指令 rmdir 和 rm 指令 man 指令手册 cp 命令 cat/echo/tac 指令 mv 指令 less 指令 head/tail 指令 date…...
Rocky Linux 9.3系统搭建Slurm环境【笔记】
实践环境:Rocky Linux 9.3 [root@m1 ~]# cat /etc/redhat-release Rocky Linux release 9.3 (Blue Onyx) [root@m1 ~]# uname -r 5.14.0-362.8.1.el9_3.x86_64 [root@m1 ~]#主机名和IP ● 控制节点m1:10.1.1.10 ● 计算节点c1:10.1.1.11 ● 计算节点c2:10.1.1.12 一、…...
原生微信小程序使用原子化tailwindcss
这里使用了第三方库来实现:https://weapp-tw.icebreaker.top/ 官方配置步骤一: https://weapp-tw.icebreaker.top/docs/quick-start/native/install 官方配置步骤二:https://weapp-tw.icebreaker.top/docs/quick-start/native/install-plugin 我下面的操作步骤跟官方步骤…...
《掌握Nmap:全面解析网络扫描与安全检测的终极指南》
nmap # 简介(帮助) 用法:nmap [扫描类型] [选项] {目标指定内容} 简介(帮助) 用法:nmap [扫描类型] [选项] {目标指定内容} 一、目标指定: 可以传入主机名、IP 地址、网络等。 例如&a…...
k8s-Informer概要解析(2)
Client-go 主要用在 k8s 控制器中 什么是 k8s Informer Informer 负责与 kubernetes APIServer 进行 Watch 操作,Watch 的资源,可以是 kubernetes 内置资源对象,也可以 CRD。 Informer 是一个带有本地缓存以及索引机制的核心工具包&#x…...
UE5基本数据类型
bool: 表示布尔值,只有两个取值:true 或 false,用于表示逻辑条件。int8: 表示 8 位的有符号整数,范围是 −128−128 到 127127。uint8: 表示 8 位的无符号整数,范围是 00 到 255255。int16: 表示 16 位的有符号整数&am…...
Next.js 系统性教学:中间件与国际化功能深入剖析
更多有关Next.js教程,请查阅: 【目录】Next.js 独立开发系列教程-CSDN博客 目录 一、Next.js 中间件 (Middleware) 功能解析 1.1 什么是中间件? 1.2 Next.js 中间件的工作机制 1.3 中间件的功能应用 身份验证与授权 请求重定向 修改请…...
鸿蒙HarmonyOS元服务应用开发实战完全指导
内容提要 元服务概述 元服务开发流程 第一个元服务开发 元服务部署与运行 一、服务概述 1、什么是元服务 在万物互联时代,人均持有设备量不断攀升,设备种类和使用场景更加多样,使得应用开发、应用入口变得更加复杂。在此背景下&#x…...
CT中的2D、MPR、VR渲染、高级临床功能
CT中的2D、MPR、VR渲染 在CT(计算机断层扫描)中,2D、MPR(多平面重建)、VR(体积渲染)是不同的图像显示和处理技术,它们各自有独特的用途和优势。下面分别介绍这三种技术:…...
利用docker-compose来搭建flink集群
1.前期准备 (1)把docker,docker-compose,kafka集群安装配置好 参考文章: 利用docker搭建kafka集群并且进行相应的实践-CSDN博客 这篇文章里面有另外两篇文章的链接,点进去就能够看到 (2&…...
力扣打卡10:K个一组翻转链表
链接:25. K 个一组翻转链表 - 力扣(LeetCode) 这道题需要在链表上,每k个为一组,翻转,链接。 乍一看好像比较容易,其实有很多细节。比如每一组反转后怎么找到上一组的新尾,怎么找到…...
深度学习详解
深度学习(Deep Learning,DL)是机器学习(Machine Learning,ML)中的一个子领域,利用多层次(深层)神经网络来自动从数据中提取特征和规律,模仿人脑的神经系统来进…...
鸿蒙分享(一):添加模块,修改app名称图标
码仓库:https://gitee.com/linguanzhong/share_harmonyos 鸿蒙api:12 新建公共模块common 在entry的oh-package.json5添加dependencies,引入common模块 "dependencies": {"common": "file:../common" } 修改app名称&…...
【Redis】not support: redis
1、查看redis进程 2、查看是否安装redis扩展,此处以宝塔为例...
【集群划分】含分布式光伏的配电网集群电压控制【33节点】
目录 主要内容 模型研究 1.节点电压灵敏度的计算 2.Kmeans聚类划分 3.集群K值 部分代码 运行结果 下载链接 主要内容 该程序参考文献《含分布式光伏的配电网集群划分和集群电压协调控制》,基于社团检测算法,实现基于电气距离和区域电压调节能…...
嵌入式蓝桥杯学习5 定时中断实现按键
Cubemx配置 打开cubemx。 前面的配置与前文一样,这里主要配置基本定时器的定时功能。 1.在Timer中点击TIM6,勾选activated。配置Parameter Settings中的预分频器(PSC)和计数器(auto-reload Register) 补…...
【Java】类似王者荣耀游戏
r77683962/WangZheYouDianRongYao 运行效果图: 类似王者荣耀游戏运行效果图_哔哩哔哩_bilibili...
C++<基本>:union是没有构造函数和析构函数的
今天发现当我在union中包含了多个结构体时,结构体有默认构造函数时,编译报错。 问题点: union不支持构造函数和析构函数union中的元素本身也是不支持构造函数和析构函数的。包含union的结构体也不支持构造函数和析构函数。 出错代码如下&a…...
IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
