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…...
MPNet:旋转机械轻量化故障诊断模型详解python代码复现
目录 一、问题背景与挑战 二、MPNet核心架构 2.1 多分支特征融合模块(MBFM) 2.2 残差注意力金字塔模块(RAPM) 2.2.1 空间金字塔注意力(SPA) 2.2.2 金字塔残差块(PRBlock) 2.3 分类器设计 三、关键技术突破 3.1 多尺度特征融合 3.2 轻量化设计策略 3.3 抗噪声…...
linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
智能仓储的未来:自动化、AI与数据分析如何重塑物流中心
当仓库学会“思考”,物流的终极形态正在诞生 想象这样的场景: 凌晨3点,某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径;AI视觉系统在0.1秒内扫描包裹信息;数字孪生平台正模拟次日峰值流量压力…...
