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

【洛谷 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+n1 行:每行两个数 苹果高度 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 n5000, a ≤ 50 a\leq 50 a50, b ≤ 200 b\leq 200 b200, s ≤ 1000 s\leq 1000 s1000, x i ≤ 280 x_i\leq 280 xi280, y i ≤ 100 y_i\leq 100 yi100


思路

将能够得着的苹果的所需体力放入多重集合中,连排序都省了。

使用贪心算法,挑需要体力最少的苹果摘,直到体力不足为止。


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】陶陶摘苹果(升级版)题解(多重集合+贪心算法)

陶陶摘苹果&#xff08;升级版&#xff09; 题目描述 又是一年秋季时&#xff0c;陶陶家的苹果树结了 n n n 个果子。陶陶又跑去摘苹果&#xff0c;这次他有一个 a a a 公分的椅子。当他手够不着时&#xff0c;他会站到椅子上再试试。 这次与 NOIp2005 普及组第一题不同的…...

使用WebSocket实现网页聊天室

一、引言 1. 问题引入 Hypertext Transfer Protocol (HTTP) 协议 一种无状态的、应用层的、以请求/应答方式运行的协议&#xff0c;它使用可扩展的语义和自描述消息格式&#xff0c;与基于网络的超文本信息系统灵活的互动. 因为http 通信只能由客户端发起,服务器返回查询结果…...

《如何控制 LLM 的输出格式和解析其输出结果?》

内容来源&#xff1a;dotey 《如何控制 LLM 的输出格式和解析其输出结果&#xff1f;》 https://baoyu.io/blog/prompt-engineering/how-to-parse-the-output-from-llm 现在很多人对于如何使用像 ChatGPT 这样的 LLM 已经比较有经验了&#xff0c;可以使用各种不同的 Prompt …...

《网络协议》07. 其他协议

title: 《网络协议》07. 其他协议 date: 2022-10-07 18:24:02 updated: 2023-11-15 08:00:52 categories: 学习记录&#xff1a;网络协议 excerpt: IPv6、WebSocket、WebService&#xff08;SOAP&#xff0c;WSDL&#xff09;、HTTPDNS、FTP、邮件&#xff08;SMTP&#xff0c;…...

高压放大器设计要求有哪些内容

设计高压放大器时&#xff0c;需要考虑一系列要求以确保其性能和可靠性。以下是设计高压放大器时的一些重要要求。 输入输出电压范围&#xff1a;高压放大器应具备足够的输入和输出电压范围&#xff0c;以适应特定应用的需求。这包括设计合适的电源供应和电路配置&#xff0c;以…...

1700亿烧光,利润暴跌78%!外媒:中芯国际不是麒麟9000S的代工厂

作为芯片代工领域的领导者&#xff0c;台积电在全球半导体市场上占据着重要的地位。然而&#xff0c;由于美国对华为的制裁&#xff0c;台积电关闭了对华为麒麟芯片的代工&#xff0c;这也引发了外界对于芯片代工模式的讨论。与此同时&#xff0c;中芯国际作为大陆规模最大、技…...

简单理解路由重分发(用两路由器来理解)

相关命令&#xff1a; default-information originate //*重分发默认路由 redistribute rip subnets //*重分发rip redistribute ospf 1 metric 3 //*重分发ospf&#xff08;其中&#xff1a;1是ospf进程id 3是跳数&#xff09; redistribute sta…...

什么是等保测评?

随着近几年随着网络技术的发展&#xff0c;互联网应用的普及和丰富&#xff0c;互联网安全问题也日益严重&#xff0c;利用信息技术进行的高科技犯罪事件呈现增长态势。从2004年度CNCERT的信息网络安全工作报告中我们看到&#xff0c;信息网络安全事故在逐年上升&#xff0c;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-计算机毕业设计项目选题推荐

摘 要 随着计算机技术的发展&#xff0c;特别是计算机网络技术与数据库技术的发展&#xff0c;使人们的生活与工作方式发生了很大的改观。本课题研究的高校实验室资产管理系统&#xff0c;主要功能模块包括后台首页&#xff0c;轮播图&#xff0c;公告管理&#xff0c;资源管理…...

高效能人士的七个习惯

今天小编给大家推荐最近读的一本书&#xff0c;史蒂芬柯维的《高效能人士的七个习惯》&#xff0c;分别是积极主动、以始为终、要事第一、双赢思维、知己解彼、综合高效及不断更新。 一、个人领域&#xff1a;从依赖到独立 习惯一&#xff1a;积极主动——个人愿景的原则付诸行…...

【前端】使用json-server报错

当我们使用json-server模仿后端接口时需要运行json-server --watch index.json这个命令生成增删改查接口但是可能会报这个错误&#xff0c;如图 这时我们运行 npm i json-server -g命令即可&#xff0c;然后再重新运行json-server --watch index.json就行了...

【Git企业开发】第七节.多人协作开发

文章目录 前言 一、多人协作开发 1.1 多人协作一 1.2 多人协作二 1.3 远程分支删除后&#xff0c;本地 git branch -a 依然能看到的解决办法 总结 前言 一、多人协作开发 1.1 多人协作一 目前&#xff0c;我们所完成的工作如下: 基本完成Git的所有本地库的相关操作&#xff0…...

行情分析——加密货币市场大盘走势(11.16)

大饼昨日突然回调诱多上涨到38000附近&#xff0c;现在又重新跌回到37500&#xff0c;现在仓位小的可以加仓入场&#xff0c;而已经有仓位的不要动即可。 空单策略&#xff1a;入场37500附近 止盈34000-32000 止损39000 以太今日可以入场空单2060附近即可 策略&#xff1a;入…...

ICCV 23丨3D-VisTA:用于 3D 视觉和文本对齐的预训练Transformer

来源&#xff1a;投稿 作者&#xff1a;橡皮 编辑&#xff1a;学姐 论文链接&#xff1a;https://arxiv.org/abs/2308.04352 开源代码&#xff1a;http://3d-vista.github.io 摘要&#xff1a; 3D视觉语言标定&#xff08;3D-VL&#xff09;是一个新兴领域&#xff0c;旨在将…...

SFP-10G-SR光模块指南

SFP-10G-SR通常是思科&#xff08;Cisco&#xff09;使用的型号名。是一种用于非常短距离应用的最低成本、最低功耗的10G SFP模块。本文汇总了初学者在第一阶段关于10G SFP SR模块的常见问题。 SFP-10G-SR模块是否支持GE&#xff1f; 10GBASE-SR模块本身是可以支持GE速度的&am…...

使用Java实现一个简单的贪吃蛇小游戏

一. 准备工作 首先获取贪吃蛇小游戏所需要的头部、身体、食物以及贪吃蛇标题等图片。 然后&#xff0c;创建贪吃蛇游戏的Java项目命名为snake_game&#xff0c;并在这个项目里创建一个文件夹命名为images&#xff0c;将图片素材导入文件夹。 再在src文件下创建两个包&#xff0…...

智能运维监控告警6大优势

随着云计算和互联网的高速发展&#xff0c;大量应用需要横跨不同网络终端&#xff0c;并广泛接入第三方服务(如支付、登录、导航等)&#xff0c;IT系统架构越来越复杂。 快速迭代的产品需求和良好的用户体验&#xff0c;需要IT运维管理者时刻保障核心业务稳定可用&#xff0c;…...

保姆级使用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>…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...

招商蛇口 | 执笔CID,启幕低密生活新境

作为中国城市生长的力量&#xff0c;招商蛇口以“美好生活承载者”为使命&#xff0c;深耕全球111座城市&#xff0c;以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子&#xff0c;招商蛇口始终与城市发展同频共振&#xff0c;以建筑诠释对土地与生活的…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

文件上传漏洞防御全攻略

要全面防范文件上传漏洞&#xff0c;需构建多层防御体系&#xff0c;结合技术验证、存储隔离与权限控制&#xff1a; &#x1f512; 一、基础防护层 前端校验&#xff08;仅辅助&#xff09; 通过JavaScript限制文件后缀名&#xff08;白名单&#xff09;和大小&#xff0c;提…...

DeepSeek越强,Kimi越慌?

被DeepSeek吊打的Kimi&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...

渗透实战PortSwigger Labs指南:自定义标签XSS和SVG XSS利用

阻止除自定义标签之外的所有标签 先输入一些标签测试&#xff0c;说是全部标签都被禁了 除了自定义的 自定义<my-tag onmouseoveralert(xss)> <my-tag idx onfocusalert(document.cookie) tabindex1> onfocus 当元素获得焦点时&#xff08;如通过点击或键盘导航&…...