【题目来源】
洛谷：P1478 陶陶摘苹果（升级版） - 洛谷
【题目描述】
又是一年秋季时，陶陶家的苹果树结了 \(n\) 个果子。陶陶又跑去摘苹果，这次他有一个 \(a\) 公分的椅子。当他手够不着时，他会站到椅子上再试试。
这次与 NOIP2005 普及组第一题不同的是：陶陶之前搬凳子，力气只剩下 \(s\) 了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在 \(s\lt 0\) 之前最多能摘到多少个苹果。
现在已知 \(n\) 个苹果到达地上的高度 \(x_i\)，椅子的高度 \(a\)，陶陶手伸直的最大长度 \(b\)，陶陶所剩的力气 \(s\)，陶陶摘一个苹果需要的力气 \(y_i\)，求陶陶最多能摘到多少个苹果。
【输入】
第 \(1\) 行：两个数 苹果数 \(n\)，力气 \(s\)。
第 \(2\) 行：两个数 椅子的高度 \(a\)，陶陶手伸直的最大长度 \(b\)。
第 \(3\) 行~第 \(3+n-1\) 行：每行两个数 苹果高度 xi，摘这个苹果需要的力气 \(y_i\)。
【输出】
只有一个整数，表示陶陶最多能摘到的苹果数。
【输入样例】
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
【输出样例】
4
【解题思路】
【代码详解】
《洛谷 P1478 陶陶摘苹果（升级版）》 #模拟# #贪心# #排序# #洛谷原创#
#include <bits/stdc++.h>
using namespace std;
int n, s, a, b, tx, ty, mark=0, y[5005], ans=0;
int main()
{cin >> n >> s >> a >> b;for (int i=1; i<=n; i++) {cin >> tx >> ty;if (tx<=a+b) {y[mark++] = ty;}}sort(y, y+mark);for (int i=0; i<mark; i++) {if (s>=y[i]) {s -= y[i];ans++;}}cout << ans << endl;return 0;
}
【运行结果】
8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2
4