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

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

可靠性+灵活性:电力载波技术在楼宇自控中的核心价值

可靠性灵活性&#xff1a;电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中&#xff0c;电力载波技术&#xff08;PLC&#xff09;凭借其独特的优势&#xff0c;正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据&#xff0c;无需额外布…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

Springboot社区养老保险系统小程序

一、前言 随着我国经济迅速发展&#xff0c;人们对手机的需求越来越大&#xff0c;各种手机软件也都在被广泛应用&#xff0c;但是对于手机进行数据信息管理&#xff0c;对于手机的各种软件也是备受用户的喜爱&#xff0c;社区养老保险系统小程序被用户普遍使用&#xff0c;为方…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

基于 TAPD 进行项目管理

起因 自己写了个小工具&#xff0c;仓库用的Github。之前在用markdown进行需求管理&#xff0c;现在随着功能的增加&#xff0c;感觉有点难以管理了&#xff0c;所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD&#xff0c;需要提供一个企业名新建一个项目&#…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

RabbitMQ 各类交换机

为什么要用交换机&#xff1f; 交换机用来路由消息。如果直发队列&#xff0c;这个消息就被处理消失了&#xff0c;那别的队列也需要这个消息怎么办&#xff1f;那就要用到交换机 交换机类型 1&#xff0c;fanout&#xff1a;广播 特点 广播所有消息​​&#xff1a;将消息…...

react更新页面数据,操作页面,双向数据绑定

// 路由不是组件的直接跳转use client&#xff0c;useEffect&#xff0c;useRouter&#xff0c;需3个结合&#xff0c; use client表示客户端 use client; import { Button,Card, Space,Tag,Table,message,Input } from antd; import { useEffect,useState } from react; impor…...