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

这篇具有很好参考价值的文章主要介绍了洛谷-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


贪心经典要素:结构体排序文章来源地址https://www.toymoban.com/news/detail-831532.html

#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+b
	int 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-陶陶摘苹果(升级版)(贪心)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 单身狗问题(初级)兼(升级版)

    所属专栏:经典算法题❤️ 🚀 博主首页:初阳785❤️ 🚀 代码托管:chuyang785❤️ 🚀 感谢大家的支持,您的点赞和关注是对我最大的支持!!!❤️ 🚀 博主也会更加的努力,创作出更优质的博文!!❤️ 🚀 关注我,关注我,关注我,重要的事情说三遍!!!!!!!!

    2024年02月16日
    浏览(43)
  • P1553 数字反转(升级版)(JAVA)

    以下为原题面,仅供参考: 给定一个数,请将该数各个位上数字反转得到一个新数。 这次与 NOIp2011 普及组第一题不同的是:这个数可以是小数,分数,百分数,整数。整数反转是将所有数位对调;小数反转是把整数部分的数反转,再将小数部分的数反转,不交换整数部分与小

    2024年02月13日
    浏览(46)
  • 云计算中网络基础知识(升级版)

    网络相连:电脑-交换机-电脑 需要配置两个地址:(1) IP地址、子网掩码、网关(网络的出口)。 (2) MAC 地址(物理地址)不需要配置,电脑网卡自带的(天生就有) 电脑必须要配置IP地址、子网掩码 才可以通信、网关可以不用(前提是两台电脑处在同一个网段下) 网关

    2023年04月27日
    浏览(44)
  • EasyExcel复杂表头导出(一对多)升级版

            在之前写的 EasyExcel复杂表头导出(一对多)的博客的结尾,受限于当时的能力和精力,留下一些问题及展望。现在写下此博客,目的就是解决之前遗留的问题。         背景介绍,见上述链接指向的博客,这里主要通过 自定义拦截器 的形式来完美解决。 对于图

    2024年02月06日
    浏览(63)
  • 【Unity+MySQL】实现注册登录系统(升级版)

    接着 上篇文章所谈到的系统缺陷,这篇文章进行升级解决。 问题 :注册界面与登录界面是同一个界面,导致用户输入用户密码进行注册后,即可点击登录。 解决 :在同一个场景中分别创建注册界面和登录界面,使用SetActive控制注册/登录成功后UI的显示与隐藏。 整体的UI框

    2024年02月09日
    浏览(50)
  • Python数据挖掘 | 升级版自动查核酸

    📕作者简介: 热爱跑步的恒川 ,致力于C/C++、Java、Python等多编程语言,热爱跑步,喜爱音乐的一位博主。 📗本文收录于恒川的日常汇报系列,大家有兴趣的可以看一看 📘相关专栏C语言初阶、C语言进阶系列、恒川等,大家有兴趣的可以看一看 📙Python零基础入门系列,J

    2024年02月08日
    浏览(46)
  • Python每日一练——第5天:闰年问题升级版

    前言 📢📢 Python每日一练来啦,本文已收录于: 《Python每日一练》专栏 此专栏目的在于,帮忙学习Python的小白提高编程能力,训练逻辑思维,每周持续更新中,欢迎免费订阅!!! 输入年月日,输出该日期是否是闰年,并且输出该日期是此年份的第几天 闰年判断条件(两

    2024年02月05日
    浏览(47)
  • 语音识别(利用python将语音转化为文字)(升级版)

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 基于语音识别(1)进行的完善,修改了60秒断触的问题,另外可以更加方便的调用,语音识别1的链接如下: https://blog.csdn.net/m0_46657126/article/details/124531081 https://www.xfyun.cn/ ps:注册账户是完全免费的,因

    2024年02月03日
    浏览(70)
  • Python-敲木鱼升级版(真手动版敲木鱼)

    演示效果 需要安装的第三方库: pip install pygame # 加载音乐 pip install pillow # 加载图片 pip install mediapipe # 判断手势的模型 pip install opencv # 模型要用来处理图形 建议有独显和摄像头的可以尝试! 想着升级一下玩法,只有真敲才能真积徳!于是找了个能判断手势的模型。 源码(

    2024年02月05日
    浏览(42)
  • SpringCloud是SpringBoot 的升级版吗?有什么区别?

    目录 一、什么是SpringBoot 二、什么是SpringCloud 三、SpringCloud是SpringBoot 的升级版吗 四、SpringCloud和SpringBoot 有什么区别   Spring Boot是一种用于快速构建基于Spring框架的Java应用程序的开发框架。它简化了Spring应用程序的配置和部署过程,提供了一种便捷的开发方式,同时也提供了

    2024年02月15日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包