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


贪心经典要素:结构体排序

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e3 + 10;struct Apple {	//定义结构体,记录苹果的高度和体力花费int height, cost;
}apple[N];bool com(Apple aa, Apple bb) {	//定义一个结构的排序方式,return aa.cost < bb.cost;	//使其sort时按照体力花费从小到大排序
}// ! ! ! return < :从小到大		return > : 从大到小int main() {			int n; cin >> n;	//s:体力,a:椅子高度,b:手伸长高度int s, a, b; cin >> s >> a >> b;//maxHeight = a+bint res = 0;	//存答案for (int i = 1; i <= n; i++) {cin >> apple[i].height >> apple[i].cost;if (apple[i].cost == 0 && apple[i].height <= a+b) {	//由于个别苹果摘得时候甚至能够只花0体力res++;											//故我们判断如果高度能够到且不用花费体力	apple[i].cost = 2e9;							//就直接让答案增加,并且使这个苹果高度无限高}													//这样保证不会被重复搜到}sort(apple + 1, apple + n + 1, com);for (int i = 1; i <= n; i++) {if (a + b >= apple[i].height && s >= apple[i].cost) {//只需要判断最大高度能够到就可以,搬椅子不会花费额外体力res++;s -= apple[i].cost;}if (s <= 0)break;		//如果体力已经没了就直接跳出}cout << res;return 0;
}

相关文章:

洛谷-P1478-陶陶摘苹果(升级版)(贪心)

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

【大数据面试题】007 谈一谈 Flink 背压

一步一个脚印&#xff0c;一天一道面试题&#xff08;有些难点的面试题不一定每天都能发&#xff0c;但每天都会写&#xff09; 什么是背压 Backpressure 在流式处理框架中&#xff0c;如果下游的处理速度&#xff0c;比上游的输入数据小&#xff0c;就会导致程序处理慢&…...

爬虫知识--01

爬虫介绍 # 爬虫的概念&#xff1a; 通过编程技术(python:request,selenium)&#xff0c;获取互联网中的数据(app&#xff0c;小程序&#xff0c;网站)&#xff0c;数据清洗(xpaht&#xff0c;lxml)后存到库中(mysql&#xff0c;redis&#xff0c;文件&#xff0c;excel&#x…...

【Azure 架构师学习笔记】- Azure Databricks (7) --Unity Catalog(UC) 基本概念和组件

本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Databricks】系列。 接上文 【Azure 架构师学习笔记】- Azure Databricks (6) - 配置Unity Catalog 前言 在以前的Databricks中&#xff0c;主要由Workspace和集群、SQL Warehouse组成&#xff0c; 这两年Databricks公…...

react【六】 React-Router 路由

文章目录 1、Router1.1 路由1.2 认识React-Router1.3 Link和NavLink1.4 Navigate1.5 Not Found页面配置1.6 路由的嵌套1.7 手动路由的跳转1.7.1 在函数式组件中使用hook1.7.2 在类组件中封装高阶组件 1.8 动态路由传递参数1.9 路由的配置文件以及懒加载 1、Router 1.1 路由 1.…...

AUTOSAR CP--chapter7从CAN网络学习Autosar通信

从CAN网络学习Autosar通信 前言缩写词CAN通信在AUTOSAR架构中的传输上位机配置 第六章总结&#xff1a;学习了如何使用工具的自动配置功能&#xff0c;位我们生成系统描述中部分ecu的BSW模块配置&#xff0c;但是自动配置的功能虽然为我们提供了极大的便利&#xff0c;我们仍然…...

NX/UG二次开发—CAM—平面铣边界准确设置方法

大家在对平面铣设置边界时&#xff0c;经常遇到边界方向与自己期望的不一致&#xff0c;有些人喜欢用检查刀路是否过切来判断&#xff0c;但是对于倒角、负余量等一些情况&#xff0c;刀路本来就是过切的。对于多边界&#xff0c;可以根据选择的曲线来起点和面的方向来确定&…...

网络安全综合实验

1.实验拓扑 在这里注意因为第四个要求配置双击热备&#xff0c;我们可以第一时间配置&#xff0c;避免二次重复配置消耗时间 4、FW1和FW3组成主备模式的双机热备 具体配置位置在系统-->高可靠性-->双机热备-->配置 这里上行链路有两组&#xff0c;分别为电信和移动&…...

QT-地形3D

QT-地形3D 一、 演示效果二、关键程序三、下载链接 一、 演示效果 二、关键程序 #include "ShaderProgram.h"namespace t3d::core {void ShaderProgram::init() {initializeOpenGLFunctions();loadShaders(); }void ShaderProgram::addShader(const QString &fil…...

C++拷贝构造函数与赋值运算符重载

顾得泉&#xff1a;个人主页 个人专栏&#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂&#xff0c;年薪百万&#xff01; 一、拷贝构造函数 1.概念 在现实生活中&#xff0c;可能存在一个与你一样的自己&#xff0c;我们称其为双胞胎。 那在创…...

全球各国海外媒体发稿新闻营销推广,英美德意法俄日韩多语言

【本篇由言同数字科技有限公司原创】随着全球市场化程度的加深&#xff0c;品牌出海成为越来越多企业的战略选择。而全球各国媒体的发稿&#xff0c;为品牌出海提供了重要的支持与推动。 第一部分&#xff1a;品牌出海的意义 品牌出海是指企业将自己的品牌、产品和服务推向全…...

将phantomjs制成docker镜像

几个前的一篇文章中介绍了phantomjsecharts生成图表图片的一种方式&#xff0c;但其部署复杂&#xff0c;制作为docker镜像运行就方便多了。文章参见&#xff1a;https://blog.csdn.net/u011943534/article/details/121524397 1、准备echarts 将上次文章中提到过下载的Echart…...

【LeetCode+JavaGuide打卡】Day20|530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先

学习目标&#xff1a; 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先 学习内容&#xff1a; 530.二叉搜索树的最小绝对差 题目链接&&文章讲解 给你一个二叉搜索树的根节点 root &#xff0c;返回 树中任意两不同节点值之间的最小差值…...

【工具类】开源照片管理工具pthtoprism

1. pthtoprism 1. pthtoprism 1.1. 安装1.2. 管理照片方式 1.2.1. 直接管理原始照片目录1.2.2. 导入照片 1.3. 界面功能1.4. 参考资料 1.1. 安装 wget https://dl.photoprism.app/docker/docker-compose.yml # 修改 docker-compose.yml 文件&#xff0c;具体参考下面内容 d…...

[ linux网络 ] 网关服务器搭建,综合应用SNAT、DNAT转换,dhcp分配、dns分离解析,nfs网络共享以及ssh免密登录

实验准备工作&#xff1a; 网关服务器安装&#xff1a;dhcp bind &#xff08;yum install -y dhcp bind bind-utlis&#xff09; server1安装&#xff1a;httpd (yum install -y httpd) 没有网络就搭建本地yum仓库或者配置网卡使其能够上网。 ( 1&#xff09;网关服务器…...

MySQL全量备份

一、实验素材 1.创建student和score表 (1) student表 create database school; use schoolCREATE TABLE student ( id INT(10) NOT NULL UNIQUE PRIMARY KEY , name VARCHAR(20) NOT NULL , sex VARCHAR(4) , birth YEAR, department VARCHAR(20) , address VARCHAR(50) );(…...

【Linux系统化学习】动静态库 | 软硬链接

目录 硬链接和软链接 硬链接 软链接 动态库和静态库 静态库 静态库的生成 静态库的使用 将库打包和使用 动态库 动态库的生成 动态库的使用 库搜索路径 硬链接和软链接 硬链接 上篇文章我们说到真正找到磁盘上的文件并不是文件名&#xff0c;而是inode。其实在…...

linux-firewalld防火墙端口转发

目的:通过统一地址实现对外同一地址暴露 1.系统配置文件开启 ipv4 端口转发 echo "net.ipv4.ip_forward 1" >> /etc/sysctl.confsysctl -p 2.查看防火墙配置端口转发之前的状态 firewall-cmd --statefirewall-cmd --list-all 3.开启 IP 伪装 firewall-cm…...

adobe软件提示This non-genuine Adobe app will be disabled soon【软件版本】

因为电脑上级路由器装了小飞机&#xff0c;导致本机电脑ps等adobe的系列软件出现了 This non-genuine Adobe app will be disabled soon&#xff0c;烦人的狠&#xff0c;之前有写过一篇通过更改host的教程&#xff0c;现在已经失效了&#xff0c;今天为大家分享一个用软件来屏…...

python coding with ChatGPT 打卡第20天| 二叉搜索树:搜索、验证、最小绝对差、众数

相关推荐 python coding with ChatGPT 打卡第12天| 二叉树&#xff1a;理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树&#xff1a;翻转…...

变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析

一、变量声明设计&#xff1a;let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 1.1 设计理念剖析 安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 let x 5; …...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

AirSim/Cosys-AirSim 游戏开发(四)外部固定位置监控相机

这个博客介绍了如何通过 settings.json 文件添加一个无人机外的 固定位置监控相机&#xff0c;因为在使用过程中发现 Airsim 对外部监控相机的描述模糊&#xff0c;而 Cosys-Airsim 在官方文档中没有提供外部监控相机设置&#xff0c;最后在源码示例中找到了&#xff0c;所以感…...

LabVIEW双光子成像系统技术

双光子成像技术的核心特性 双光子成像通过双低能量光子协同激发机制&#xff0c;展现出显著的技术优势&#xff1a; 深层组织穿透能力&#xff1a;适用于活体组织深度成像 高分辨率观测性能&#xff1a;满足微观结构的精细研究需求 低光毒性特点&#xff1a;减少对样本的损伤…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...