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
48
49
50
51
52
53
54
55
56
57
58
59
60#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;

struct Dwarf {
    int a, b;
} d[MAXN], ord[MAXN];

int n, H;
int best_answer;
int total_a;

bool cmp_dwarf(const Dwarf &lhs, const Dwarf &rhs) {
    return lhs.a + lhs.b < rhs.a + rhs.b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 做法是枚举所有子集，把选中的人按 a+b 排序，
    // 再逐个检查“已逃走肩高前缀 <= T+a_i+b_i-H”是否始终成立。
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> d[i].a >> d[i].b;
        total_a += d[i].a;
    }
    cin >> H;

    best_answer = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                ord[cnt++] = d[i];
            }
        }

        sort(ord, ord + cnt, cmp_dwarf);

        bool ok = true;
        int prefix_escape = 0;
        for (int i = 0; i < cnt; i++) {
            prefix_escape += ord[i].a;
            if (prefix_escape > total_a + ord[i].a + ord[i].b - H) {
                ok = false;
                break;
            }
        }

        if (ok) {
            best_answer = max(best_answer, cnt);
        }
    }

    cout << best_answer << '\n';
    return 0;
}

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
48
49
50
51
52
53
54
55
56
57
58#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2005;

struct Dwarf {
    int a, b; // a 表示肩高，b 表示手臂长度
} d[MAXN];

int n, H;
long long total_a; // 所有小矮人肩高总和 T

bool cmp_dwarf(const Dwarf &lhs, const Dwarf &rhs) {
    return lhs.a + lhs.b < rhs.a + rhs.b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> d[i].a >> d[i].b;
        total_a += d[i].a;
    }
    cin >> H;

    // 按 a+b 从小到大排序。
    // 交换论证可以证明：如果两个人都要逃走，让 a+b 更小的人更早逃走不会更差。
    sort(d + 1, d + n + 1, cmp_dwarf);

    priority_queue<int> heap; // 已选小矮人的肩高，超限制时删掉最大的
    long long used = 0;       // 当前已选小矮人的肩高和

    for (int i = 1; i <= n; i++) {
        // 如果第 i 个小矮人作为当前顺序里最后一个逃走的人，
        // 那么已逃走肩高前缀 P 需要满足：
        // P <= T + a_i + b_i - H
        long long limit = total_a + d[i].a + d[i].b - H;
        if (limit < 0) {
            continue;
        }

        // 先尝试把当前小矮人加入答案集合。
        used += d[i].a;
        heap.push(d[i].a);

        // 如果当前前缀肩高和超过限制，
        // 贪心地删掉已选中肩高最大的那个人，最有利于保留更多人数。
        while (!heap.empty() && used > limit) {
            used -= heap.top();
            heap.pop();
        }
    }

    cout << (int) heap.size() << '\n';
    return 0;
}