Problem D: 小明摘苹果

Problem D: 小明摘苹果

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

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

思路:

  • 只能摘自己够得到的苹果
  • 优先摘体力消耗低的苹果
  • 采摘顺序不影响结果