当前位置: 首页 > 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…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

拉力测试cuda pytorch 把 4070显卡拉满

import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试&#xff0c;通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小&#xff0c;增大可提高计算复杂度duration: 测试持续时间&#xff08;秒&…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

AI语音助手的Python实现

引言 语音助手(如小爱同学、Siri)通过语音识别、自然语言处理(NLP)和语音合成技术,为用户提供直观、高效的交互体验。随着人工智能的普及,Python开发者可以利用开源库和AI模型,快速构建自定义语音助手。本文由浅入深,详细介绍如何使用Python开发AI语音助手,涵盖基础功…...

区块链技术概述

区块链技术是一种去中心化、分布式账本技术&#xff0c;通过密码学、共识机制和智能合约等核心组件&#xff0c;实现数据不可篡改、透明可追溯的系统。 一、核心技术 1. 去中心化 特点&#xff1a;数据存储在网络中的多个节点&#xff08;计算机&#xff09;&#xff0c;而非…...

OCR MLLM Evaluation

为什么需要评测体系&#xff1f;——背景与矛盾 ​​ 能干的事&#xff1a;​​ 看清楚发票、身份证上的字&#xff08;准确率>90%&#xff09;&#xff0c;速度飞快&#xff08;眨眼间完成&#xff09;。​​干不了的事&#xff1a;​​ 碰到复杂表格&#xff08;合并单元…...