Problem D: 小明摘苹果
[Creator : ]
Description
又是一年秋季时,小明家的苹果树结了 个果子。小明又跑去摘苹果,这次他有一个 公分的椅子。当他手够不着时,他会站到椅子上再试试。
小明之前搬凳子,力气只剩下 了。当然,每次摘苹果时都要用一定的力气。小明想知道在 之前最多能摘到多少个苹果。
现在已知 个苹果到达地上的高度 ,椅子的高度 ,小明手伸直的最大长度 ,小明所剩的力气 ,小明摘一个苹果需要的力气 ,求小明最多能摘到多少个苹果。
#include <bits/stdc++.h>
using namespace std;
struct Apple {
int x; // 高度
int y; // 所需体力
} app [5010];
bool cmp(Apple &a, Apple &b) {
return ___________;
}
int main() {
int n, s, a, b;
cin >> n >> s;
cin >> a >> b;
for (int i = 1; i <= n; i++)
cin >> app[i].x >> app[i].y;
sort(_______________);
int ans = 0;
for (int i = 1; i <= n; i++) {
if (____________)
continue;
if (_________) {
s -= app[i].y;
ans++;
} else break;
}
cout << ans << endl;
return 0;
}
Input
第 行:两个数,苹果数 ,力气 。
第 行:两个数,椅子的高度 ,小明手伸直的最大长度 。
第 行~第 行:每行两个数,苹果高度 ,摘这个苹果需要的力气 。
对于 的数据,, , , , , 。
Output
只有一个整数,表示小明最多能摘到的苹果数。
Sample Input Copy
10 20
30 120
140 3
160 5
120 2
170 8
130 4
180 6
110 1
190 7
200 10
150 4
Sample Output Copy
5
HINT
思路:
- 只能摘自己够得到的苹果
- 优先摘体力消耗低的苹果
- 采摘顺序不影响结果