【洛谷 P1478】陶陶摘苹果(升级版)题解(多重集合+贪心算法)
陶陶摘苹果(升级版)
题目描述
又是一年秋季时,陶陶家的苹果树结了 n n n 个果子。陶陶又跑去摘苹果,这次他有一个 a a a 公分的椅子。当他手够不着时,他会站到椅子上再试试。
这次与 NOIp2005 普及组第一题不同的是:陶陶之前搬凳子,力气只剩下 s s s 了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在 s < 0 s<0 s<0 之前最多能摘到多少个苹果。
现在已知 n n n 个苹果到达地上的高度 x i x_i xi,椅子的高度 a a a,陶陶手伸直的最大长度 b b b,陶陶所剩的力气 s s s,陶陶摘一个苹果需要的力气 y i y_i yi,求陶陶最多能摘到多少个苹果。
输入格式
第 1 1 1 行:两个数 苹果数 n n n,力气 s s s。
第 2 2 2 行:两个数 椅子的高度 a a a,陶陶手伸直的最大长度 b b b。
第 3 3 3 行~第 3 + n − 1 3+n-1 3+n−1 行:每行两个数 苹果高度 x i x_i xi,摘这个苹果需要的力气 y i y_i yi。
输出格式
只有一个整数,表示陶陶最多能摘到的苹果数。
样例 #1
样例输入 #1
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
样例输出 #1
4
提示
对于 100 % 100\% 100% 的数据, n ≤ 5000 n\leq 5000 n≤5000, a ≤ 50 a\leq 50 a≤50, b ≤ 200 b\leq 200 b≤200, s ≤ 1000 s\leq 1000 s≤1000, x i ≤ 280 x_i\leq 280 xi≤280, y i ≤ 100 y_i\leq 100 yi≤100。
思路
将能够得着的苹果的所需体力放入多重集合中,连排序都省了。
使用贪心算法,挑需要体力最少的苹果摘,直到体力不足为止。
AC代码
#include <iostream>
#include <algorithm>
#include <set>
#define AUTHOR "HEX9CF"
using namespace std;const int N = 1e4 + 7;/*
n 苹果数
s 力气
a 椅子高度
b 手长
*/
int n, s, a, b;
int cnt;multiset<int> ms;int main()
{cnt = 0;cin >> n >> s >> a >> b;while (n--){int tx, ty;cin >> tx >> ty;if (tx <= a + b){ms.insert(ty);}}for (auto it = ms.begin(); it != ms.end(); it++){int ss = s - *it;if (ss < 0){break;}s = ss;cnt++;}cout << cnt << endl;return 0;
}
相关文章:
【洛谷 P1478】陶陶摘苹果(升级版)题解(多重集合+贪心算法)
陶陶摘苹果(升级版) 题目描述 又是一年秋季时,陶陶家的苹果树结了 n n n 个果子。陶陶又跑去摘苹果,这次他有一个 a a a 公分的椅子。当他手够不着时,他会站到椅子上再试试。 这次与 NOIp2005 普及组第一题不同的…...
使用WebSocket实现网页聊天室
一、引言 1. 问题引入 Hypertext Transfer Protocol (HTTP) 协议 一种无状态的、应用层的、以请求/应答方式运行的协议,它使用可扩展的语义和自描述消息格式,与基于网络的超文本信息系统灵活的互动. 因为http 通信只能由客户端发起,服务器返回查询结果…...
《如何控制 LLM 的输出格式和解析其输出结果?》
内容来源:dotey 《如何控制 LLM 的输出格式和解析其输出结果?》 https://baoyu.io/blog/prompt-engineering/how-to-parse-the-output-from-llm 现在很多人对于如何使用像 ChatGPT 这样的 LLM 已经比较有经验了,可以使用各种不同的 Prompt …...
《网络协议》07. 其他协议
title: 《网络协议》07. 其他协议 date: 2022-10-07 18:24:02 updated: 2023-11-15 08:00:52 categories: 学习记录:网络协议 excerpt: IPv6、WebSocket、WebService(SOAP,WSDL)、HTTPDNS、FTP、邮件(SMTP,…...
高压放大器设计要求有哪些内容
设计高压放大器时,需要考虑一系列要求以确保其性能和可靠性。以下是设计高压放大器时的一些重要要求。 输入输出电压范围:高压放大器应具备足够的输入和输出电压范围,以适应特定应用的需求。这包括设计合适的电源供应和电路配置,以…...
1700亿烧光,利润暴跌78%!外媒:中芯国际不是麒麟9000S的代工厂
作为芯片代工领域的领导者,台积电在全球半导体市场上占据着重要的地位。然而,由于美国对华为的制裁,台积电关闭了对华为麒麟芯片的代工,这也引发了外界对于芯片代工模式的讨论。与此同时,中芯国际作为大陆规模最大、技…...
简单理解路由重分发(用两路由器来理解)
相关命令: default-information originate //*重分发默认路由 redistribute rip subnets //*重分发rip redistribute ospf 1 metric 3 //*重分发ospf(其中:1是ospf进程id 3是跳数) redistribute sta…...
什么是等保测评?
随着近几年随着网络技术的发展,互联网应用的普及和丰富,互联网安全问题也日益严重,利用信息技术进行的高科技犯罪事件呈现增长态势。从2004年度CNCERT的信息网络安全工作报告中我们看到,信息网络安全事故在逐年上升,20…...
21、Flink 的table API与DataStream API 集成(1)- 介绍及入门示例、集成说明
Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…...
(免费领源码)Java#SpringBoot#mysql高校实验室资产管理系统85189-计算机毕业设计项目选题推荐
摘 要 随着计算机技术的发展,特别是计算机网络技术与数据库技术的发展,使人们的生活与工作方式发生了很大的改观。本课题研究的高校实验室资产管理系统,主要功能模块包括后台首页,轮播图,公告管理,资源管理…...
高效能人士的七个习惯
今天小编给大家推荐最近读的一本书,史蒂芬柯维的《高效能人士的七个习惯》,分别是积极主动、以始为终、要事第一、双赢思维、知己解彼、综合高效及不断更新。 一、个人领域:从依赖到独立 习惯一:积极主动——个人愿景的原则付诸行…...
【前端】使用json-server报错
当我们使用json-server模仿后端接口时需要运行json-server --watch index.json这个命令生成增删改查接口但是可能会报这个错误,如图 这时我们运行 npm i json-server -g命令即可,然后再重新运行json-server --watch index.json就行了...
【Git企业开发】第七节.多人协作开发
文章目录 前言 一、多人协作开发 1.1 多人协作一 1.2 多人协作二 1.3 远程分支删除后,本地 git branch -a 依然能看到的解决办法 总结 前言 一、多人协作开发 1.1 多人协作一 目前,我们所完成的工作如下: 基本完成Git的所有本地库的相关操作࿰…...
行情分析——加密货币市场大盘走势(11.16)
大饼昨日突然回调诱多上涨到38000附近,现在又重新跌回到37500,现在仓位小的可以加仓入场,而已经有仓位的不要动即可。 空单策略:入场37500附近 止盈34000-32000 止损39000 以太今日可以入场空单2060附近即可 策略:入…...
ICCV 23丨3D-VisTA:用于 3D 视觉和文本对齐的预训练Transformer
来源:投稿 作者:橡皮 编辑:学姐 论文链接:https://arxiv.org/abs/2308.04352 开源代码:http://3d-vista.github.io 摘要: 3D视觉语言标定(3D-VL)是一个新兴领域,旨在将…...
SFP-10G-SR光模块指南
SFP-10G-SR通常是思科(Cisco)使用的型号名。是一种用于非常短距离应用的最低成本、最低功耗的10G SFP模块。本文汇总了初学者在第一阶段关于10G SFP SR模块的常见问题。 SFP-10G-SR模块是否支持GE? 10GBASE-SR模块本身是可以支持GE速度的&am…...
使用Java实现一个简单的贪吃蛇小游戏
一. 准备工作 首先获取贪吃蛇小游戏所需要的头部、身体、食物以及贪吃蛇标题等图片。 然后,创建贪吃蛇游戏的Java项目命名为snake_game,并在这个项目里创建一个文件夹命名为images,将图片素材导入文件夹。 再在src文件下创建两个包࿰…...
智能运维监控告警6大优势
随着云计算和互联网的高速发展,大量应用需要横跨不同网络终端,并广泛接入第三方服务(如支付、登录、导航等),IT系统架构越来越复杂。 快速迭代的产品需求和良好的用户体验,需要IT运维管理者时刻保障核心业务稳定可用,…...
保姆级使用Vue-count-to
安装 npm install vue-count-to 直接使用 <template><div class"vue-count-to"><div class"count-to"><div><CountTo :startValstartVal :endValendVal :durationduration /></div><div><CountTo :startV…...
install YAPI MongoDB 备份mongo 安装yapi插件cross-request 笔记
登录容器 docker exec -it mongodb bash 登录mongo mongo -u root -p 123456 查看db show dbs 查看collection show collections 进入db use yapi 查看数据 db.<collection_name>.find() 带条件查看 db.<collection_name>.find({ <field>: <value>…...
智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)
安全领域各种资源,学习文档,以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具,欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
LabVIEW双光子成像系统技术
双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制,展现出显著的技术优势: 深层组织穿透能力:适用于活体组织深度成像 高分辨率观测性能:满足微观结构的精细研究需求 低光毒性特点:减少对样本的损伤…...
WEB3全栈开发——面试专业技能点P7前端与链上集成
一、Next.js技术栈 ✅ 概念介绍 Next.js 是一个基于 React 的 服务端渲染(SSR)与静态网站生成(SSG) 框架,由 Vercel 开发。它简化了构建生产级 React 应用的过程,并内置了很多特性: ✅ 文件系…...
