陶陶摘苹果（升级版）

题意

陶陶手长 b，椅子高 a，所以最高能摘到 a+b 的苹果。每个苹果有高度 x_i 和消耗体力 y_i，总力气为 s。问在力气不为负的前提下最多能摘多少个苹果。

思路

苹果之间没有依赖关系，只需要考虑两个条件：

高度 x_i <= a+b，否则无论如何摘不到；
摘苹果会消耗 y_i 点体力。

想让数量最多，就应该在所有够得到的苹果里，优先摘消耗体力最少的。若某个更贵的苹果被选择，而一个更便宜的可摘苹果没有被选择，把贵的换成便宜的，摘到的数量不变，消耗体力更少。因此按体力消耗升序贪心是安全的。

做法：

计算最高可达高度 a+b；
只保留够得到的苹果的体力消耗；
对这些消耗排序；
从小到大累加，直到剩余体力不足。

Python 知识

读取整份整数输入后，用下标 pos 每次取一对 (height, cost)。
costs.sort() 会原地升序排序，适合后续贪心扫描。
break 表示当前最便宜的剩余苹果都摘不起，后面更贵的也不用看。

这题是排序贪心模板，不需要额外暴力代码；过程文档中记录了跳过 brute.py 的原因。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n, strength = data[0], data[1]
    chair, arm = data[2], data[3]
    reachable_height = chair + arm

    costs = []
    pos = 4
    for _ in range(n):
        height, cost = data[pos], data[pos + 1]
        pos += 2
        if height <= reachable_height:
            costs.append(cost)

    costs.sort()

    answer = 0
    for cost in costs:
        if strength < cost:
            break
        strength -= cost
        answer += 1

    print(answer)


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

/* P1478 陶陶摘苹果（升级版） */
/* 先筛掉够不到的苹果，再按消耗体力从小到大贪心摘。 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5005;

int n, strength, chair, arm;
int cost[MAXN]; // 够得到的苹果的体力消耗
int cnt;        // 够得到的苹果数量

int main() {
    cin >> n >> strength;
    cin >> chair >> arm;
    int max_height = chair + arm;

    for (int i = 1; i <= n; i++) {
        int h, c;
        cin >> h >> c;
        // 只保留够得到的苹果
        if (h <= max_height) {
            cost[++cnt] = c;
        }
    }

    // 按体力消耗升序排序
    sort(cost + 1, cost + cnt + 1);

    int ans = 0;
    for (int i = 1; i <= cnt; i++) {
        if (strength < cost[i]) break; // 体力不够了
        strength -= cost[i];
        ans++;
    }

    cout << ans << "\n";
    return 0;
}

复杂度

筛选苹果是 $O(n)$ ，排序是 $O(n \log n)$ ，总时间复杂度是 $O(n \log n)$ 。

空间复杂度是 $O(n)$ 。

总结

先过滤不可选对象，再对可选对象按代价从小到大取，是“最多选择数量”问题中很常见的贪心形态。

陶陶摘苹果（升级版）

目录

题意

思路

Python 知识

代码

复杂度

总结