洛谷-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。
贪心经典要素:结构体排序
#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-陶陶摘苹果(升级版)(贪心)
陶陶摘苹果(升级版) 题目描述 又是一年秋季时,陶陶家的苹果树结了 n n n 个果子。陶陶又跑去摘苹果,这次他有一个 a a a 公分的椅子。当他手够不着时,他会站到椅子上再试试。 这次与 NOIp2005 普及组第一题不同的…...
【大数据面试题】007 谈一谈 Flink 背压
一步一个脚印,一天一道面试题(有些难点的面试题不一定每天都能发,但每天都会写) 什么是背压 Backpressure 在流式处理框架中,如果下游的处理速度,比上游的输入数据小,就会导致程序处理慢&…...
爬虫知识--01
爬虫介绍 # 爬虫的概念: 通过编程技术(python:request,selenium),获取互联网中的数据(app,小程序,网站),数据清洗(xpaht,lxml)后存到库中(mysql,redis,文件,excel&#x…...
【Azure 架构师学习笔记】- Azure Databricks (7) --Unity Catalog(UC) 基本概念和组件
本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Databricks】系列。 接上文 【Azure 架构师学习笔记】- Azure Databricks (6) - 配置Unity Catalog 前言 在以前的Databricks中,主要由Workspace和集群、SQL Warehouse组成, 这两年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架构中的传输上位机配置 第六章总结:学习了如何使用工具的自动配置功能,位我们生成系统描述中部分ecu的BSW模块配置,但是自动配置的功能虽然为我们提供了极大的便利,我们仍然…...
NX/UG二次开发—CAM—平面铣边界准确设置方法
大家在对平面铣设置边界时,经常遇到边界方向与自己期望的不一致,有些人喜欢用检查刀路是否过切来判断,但是对于倒角、负余量等一些情况,刀路本来就是过切的。对于多边界,可以根据选择的曲线来起点和面的方向来确定&…...
网络安全综合实验
1.实验拓扑 在这里注意因为第四个要求配置双击热备,我们可以第一时间配置,避免二次重复配置消耗时间 4、FW1和FW3组成主备模式的双机热备 具体配置位置在系统-->高可靠性-->双机热备-->配置 这里上行链路有两组,分别为电信和移动&…...
QT-地形3D
QT-地形3D 一、 演示效果二、关键程序三、下载链接 一、 演示效果 二、关键程序 #include "ShaderProgram.h"namespace t3d::core {void ShaderProgram::init() {initializeOpenGLFunctions();loadShaders(); }void ShaderProgram::addShader(const QString &fil…...
C++拷贝构造函数与赋值运算符重载
顾得泉:个人主页 个人专栏:《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》 键盘敲烂,年薪百万! 一、拷贝构造函数 1.概念 在现实生活中,可能存在一个与你一样的自己,我们称其为双胞胎。 那在创…...
全球各国海外媒体发稿新闻营销推广,英美德意法俄日韩多语言
【本篇由言同数字科技有限公司原创】随着全球市场化程度的加深,品牌出海成为越来越多企业的战略选择。而全球各国媒体的发稿,为品牌出海提供了重要的支持与推动。 第一部分:品牌出海的意义 品牌出海是指企业将自己的品牌、产品和服务推向全…...
将phantomjs制成docker镜像
几个前的一篇文章中介绍了phantomjsecharts生成图表图片的一种方式,但其部署复杂,制作为docker镜像运行就方便多了。文章参见:https://blog.csdn.net/u011943534/article/details/121524397 1、准备echarts 将上次文章中提到过下载的Echart…...
【LeetCode+JavaGuide打卡】Day20|530.二叉搜索树的最小绝对差、501.二叉搜索树中的众数、236. 二叉树的最近公共祖先
学习目标: 530.二叉搜索树的最小绝对差 501.二叉搜索树中的众数 236. 二叉树的最近公共祖先 学习内容: 530.二叉搜索树的最小绝对差 题目链接&&文章讲解 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值…...
【工具类】开源照片管理工具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 文件,具体参考下面内容 d…...
[ linux网络 ] 网关服务器搭建,综合应用SNAT、DNAT转换,dhcp分配、dns分离解析,nfs网络共享以及ssh免密登录
实验准备工作: 网关服务器安装:dhcp bind (yum install -y dhcp bind bind-utlis) server1安装:httpd (yum install -y httpd) 没有网络就搭建本地yum仓库或者配置网卡使其能够上网。 ( 1)网关服务器…...
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系统化学习】动静态库 | 软硬链接
目录 硬链接和软链接 硬链接 软链接 动态库和静态库 静态库 静态库的生成 静态库的使用 将库打包和使用 动态库 动态库的生成 动态库的使用 库搜索路径 硬链接和软链接 硬链接 上篇文章我们说到真正找到磁盘上的文件并不是文件名,而是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【软件版本】
因为电脑上级路由器装了小飞机,导致本机电脑ps等adobe的系列软件出现了 This non-genuine Adobe app will be disabled soon,烦人的狠,之前有写过一篇通过更改host的教程,现在已经失效了,今天为大家分享一个用软件来屏…...
python coding with ChatGPT 打卡第20天| 二叉搜索树:搜索、验证、最小绝对差、众数
相关推荐 python coding with ChatGPT 打卡第12天| 二叉树:理论基础 python coding with ChatGPT 打卡第13天| 二叉树的深度优先遍历 python coding with ChatGPT 打卡第14天| 二叉树的广度优先遍历 python coding with ChatGPT 打卡第15天| 二叉树:翻转…...
idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
【Java学习笔记】Arrays类
Arrays 类 1. 导入包:import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序(自然排序和定制排序)Arrays.binarySearch()通过二分搜索法进行查找(前提:数组是…...
IGP(Interior Gateway Protocol,内部网关协议)
IGP(Interior Gateway Protocol,内部网关协议) 是一种用于在一个自治系统(AS)内部传递路由信息的路由协议,主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...
MVC 数据库
MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...
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任务 三、…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
