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

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≤1
0^9,1≤Di≤Li10^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/【题目描述】 在小蓝的生日那天&#xff0c;他得到了一个由神秘人赠送的拼图游戏&#xff0c;每个拼图都有其特定的价值和相应的优惠券。小蓝决定要买下所有的拼图&#xff0c;但他希望能尽可能地节省花费。小蓝手中…...

Spring Boot教程之二十一:文件处理

Spring Boot – 文件处理 Spring Boot 是一种流行的、基于 Spring 的开源框架&#xff0c;用于开发强大的 Web 应用程序和微服务。由于它建立在 Spring 框架之上&#xff0c;因此它不仅具有 Spring 的所有功能&#xff0c;而且还包括某些特殊功能&#xff0c;例如自动配置、健康…...

【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 # 简介&#xff08;帮助&#xff09; 用法&#xff1a;nmap [扫描类型] [选项] {目标指定内容} 简介&#xff08;帮助&#xff09; 用法&#xff1a;nmap [扫描类型] [选项] {目标指定内容} 一、目标指定&#xff1a; 可以传入主机名、IP 地址、网络等。 例如&a…...

k8s-Informer概要解析(2)

Client-go 主要用在 k8s 控制器中 什么是 k8s Informer Informer 负责与 kubernetes APIServer 进行 Watch 操作&#xff0c;Watch 的资源&#xff0c;可以是 kubernetes 内置资源对象&#xff0c;也可以 CRD。 Informer 是一个带有本地缓存以及索引机制的核心工具包&#x…...

UE5基本数据类型

bool: 表示布尔值&#xff0c;只有两个取值&#xff1a;true 或 false&#xff0c;用于表示逻辑条件。int8: 表示 8 位的有符号整数&#xff0c;范围是 −128−128 到 127127。uint8: 表示 8 位的无符号整数&#xff0c;范围是 00 到 255255。int16: 表示 16 位的有符号整数&am…...

Next.js 系统性教学:中间件与国际化功能深入剖析

更多有关Next.js教程&#xff0c;请查阅&#xff1a; 【目录】Next.js 独立开发系列教程-CSDN博客 目录 一、Next.js 中间件 (Middleware) 功能解析 1.1 什么是中间件&#xff1f; 1.2 Next.js 中间件的工作机制 1.3 中间件的功能应用 身份验证与授权 请求重定向 修改请…...

鸿蒙HarmonyOS元服务应用开发实战完全指导

内容提要 元服务概述 元服务开发流程 第一个元服务开发 元服务部署与运行 一、服务概述 1、什么是元服务 在万物互联时代&#xff0c;人均持有设备量不断攀升&#xff0c;设备种类和使用场景更加多样&#xff0c;使得应用开发、应用入口变得更加复杂。在此背景下&#x…...

CT中的2D、MPR、VR渲染、高级临床功能

CT中的2D、MPR、VR渲染 在CT&#xff08;计算机断层扫描&#xff09;中&#xff0c;2D、MPR&#xff08;多平面重建&#xff09;、VR&#xff08;体积渲染&#xff09;是不同的图像显示和处理技术&#xff0c;它们各自有独特的用途和优势。下面分别介绍这三种技术&#xff1a;…...

利用docker-compose来搭建flink集群

1.前期准备 &#xff08;1&#xff09;把docker&#xff0c;docker-compose&#xff0c;kafka集群安装配置好 参考文章&#xff1a; 利用docker搭建kafka集群并且进行相应的实践-CSDN博客 这篇文章里面有另外两篇文章的链接&#xff0c;点进去就能够看到 &#xff08;2&…...

力扣打卡10:K个一组翻转链表

链接&#xff1a;25. K 个一组翻转链表 - 力扣&#xff08;LeetCode&#xff09; 这道题需要在链表上&#xff0c;每k个为一组&#xff0c;翻转&#xff0c;链接。 乍一看好像比较容易&#xff0c;其实有很多细节。比如每一组反转后怎么找到上一组的新尾&#xff0c;怎么找到…...

深度学习详解

深度学习&#xff08;Deep Learning&#xff0c;DL&#xff09;是机器学习&#xff08;Machine Learning&#xff0c;ML&#xff09;中的一个子领域&#xff0c;利用多层次&#xff08;深层&#xff09;神经网络来自动从数据中提取特征和规律&#xff0c;模仿人脑的神经系统来进…...

鸿蒙分享(一):添加模块,修改app名称图标

码仓库&#xff1a;https://gitee.com/linguanzhong/share_harmonyos 鸿蒙api:12 新建公共模块common 在entry的oh-package.json5添加dependencies&#xff0c;引入common模块 "dependencies": {"common": "file:../common" } 修改app名称&…...

【Redis】not support: redis

1、查看redis进程 2、查看是否安装redis扩展&#xff0c;此处以宝塔为例...

【集群划分】含分布式光伏的配电网集群电压控制【33节点】

目录 主要内容 模型研究 1.节点电压灵敏度的计算 2.Kmeans聚类划分 3.集群K值 部分代码 运行结果 下载链接 主要内容 该程序参考文献《含分布式光伏的配电网集群划分和集群电压协调控制》&#xff0c;基于社团检测算法&#xff0c;实现基于电气距离和区域电压调节能…...

嵌入式蓝桥杯学习5 定时中断实现按键

Cubemx配置 打开cubemx。 前面的配置与前文一样&#xff0c;这里主要配置基本定时器的定时功能。 1.在Timer中点击TIM6&#xff0c;勾选activated。配置Parameter Settings中的预分频器&#xff08;PSC&#xff09;和计数器&#xff08;auto-reload Register&#xff09; 补…...

【Java】类似王者荣耀游戏

r77683962/WangZheYouDianRongYao 运行效果图&#xff1a; 类似王者荣耀游戏运行效果图_哔哩哔哩_bilibili...

C++<基本>:union是没有构造函数和析构函数的

今天发现当我在union中包含了多个结构体时&#xff0c;结构体有默认构造函数时&#xff0c;编译报错。 问题点&#xff1a; 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服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

基础测试工具使用经验

背景 vtune&#xff0c;perf, nsight system等基础测试工具&#xff0c;都是用过的&#xff0c;但是没有记录&#xff0c;都逐渐忘了。所以写这篇博客总结记录一下&#xff0c;只要以后发现新的用法&#xff0c;就记得来编辑补充一下 perf 比较基础的用法&#xff1a; 先改这…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

[Java恶补day16] 238.除自身以外数组的乘积

给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O(n) 时间复杂度…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...