SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 19 题

三、完善程序（单选题，每小题 $3$ 分，共计 $30$ 分）

1.（装备穿戴问题） 有 $n$ 件装备，穿戴第 $i$ 件装备需要玩家的力量值至少为 $a_i$，穿戴该装备后会让玩家的力量值增加 $b_i$。现在请问玩家的初始力量值最小是多少，才能以某种顺序穿戴上所有的装备？

输入：第一行是一个整数 $n(1 \leq n \leq 10^3)$；第二行有 $n$ 个整数，第 $i$ 个整数表示 $a_i(0 \leq a_i \leq 10^9)$；第三行有 $n$ 个整数，第 $i$ 个整数表示 $b_i(0 \leq b_i \leq 10^6)$。

提示：使用二分+贪心的方法解决这个问题，先对装备按顺序进行排序，然后二分答案，并贪心地进行选择。

试补全程序。

#include <cstdio>
#include <algorithm>

using namespace std;
const int maxn = 1005;

int n;
int a[maxn], b[maxn], c[maxn];

bool Comp(const int &x, const int &y) { 
    // 你可以简单地认为括号内的内容等价于 (int x, int y)
    return ①;
}

bool check(int x) {
    for (int i = 1; i <= n; ++i) {
        int u = c[i];
        if (②) {
            x += b[u];
        } else {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是二分答案配合贪心策略。拿到题先想：能不能穿完所有装备？把装备按‘需要力量从小到大’排好序，然后二分一个初始力量值，用这个值去模拟穿戴过程，看能否全部成功。

最容易掉进两个坑：一是排序方向搞反，把需求大的放前面，导致后面根本穿不上；二是检查函数里用错下标，c[i]存的是原始编号，判断条件却写成 x >= a[i]，这里 i 是排序后的位置，必须用 c[i] 去查原始数组 a。还有一个细节，二分循环条件写 l < r 时，若 check(mid) 成立，mid 可能是最优解，但 r 应该设为 mid-1 继续往左找更小的；若写错成 r=mid，会导致死循环或答案偏大。

这道题考查的是二分答案与贪心策略的结合应用，核心在于理解‘穿戴顺序’对可行性判断的影响，以及如何通过二分缩小初始力量值的搜索范围。

首先，我们要明确题目的本质：给定 n 件装备，每件装备 i 需要力量 a[i]，穿戴后力量增加 b[i]。问初始力量至少是多少才能按某种顺序穿完所有装备。这里有一个关键的贪心直觉：为了让后续装备更容易穿，我们应该优先穿那些‘需求低’的装备。因为穿得越多，力量增长越多，后面高需求的装备就越有可能被满足。所以，第一步必须对所有装备按照 a[i] 从小到大排序。如果 a[i] 相同，题目没有特殊要求，按任意顺序均可（因为穿哪个都不影响当前力量，只影响后续力量增量，而增量是固定的）。因此，题目中 Comp 函数的排序条件应当是 a[x] < a[y]，对应选项 B。

接下来，我们考虑如何验证某个初始力量值 x 是否可行。这就是 check 函数的任务。排序后，我们依次遍历 c[1] 到 c[n]（c 数组存的是原始编号）。对于第 i 个装备（即 c[i] 对应的那件），我们需要当前力量 x 至少达到 a[c[i]]。如果 x < a[c[i]]，说明即使穿到了这里也穿不上，直接返回 false。如果穿得上，力量就会增加 b[c[i]]，即 x += b[c[i]]。注意这里必须用 c[i] 去查 a 和 b，因为 i 只是排序后的下标，而 a 和 b 是按原始下标存储的。很多同学容易在这里出错，写成 x >= a[i]，这是典型的‘下标错位’错误，对应选项 D 的正确写法。

既然验证一个 x 的时间复杂度是 O(n)，而 x 的范围可能很大（a[i] 可达 10^9），我们不能线性枚举。这时候二分答案就登场了。我们要找的是最小的可行 x。二分的初始范围可以设为 [1, 2e9]（因为最大需求是 10^9，穿一件最多增加 10^6，1000 件最多增加 10^9，所以 2e9 足够覆盖）。二分循环的条件是 l <= r，这样当区间缩小到 l == r 时，check(l) 一定成立，而 check(l-1) 一定不成立（否则 l 就不是最小了）。如果写成 l < r，当 l == r 时循环会提前结束，可能漏掉最优解，或者在 check(mid) 成立时错误地让 r = mid，导致死循环。因此，循环条件应选 B。

在二分过程中，mid = (l + r) / 2。如果 check(mid) 为真，说明 mid 可行，但可能还有更小的可行值，所以我们要尝试更小的区间，即 r = mid - 1，同时记录 ans = mid。如果 check(mid) 为假，说明 mid 太小，必须往右找，即 l = mid + 1。注意这里不能把 r = mid 当作可行，因为 mid 已经验证失败，它比任何更小的数都大，但既然它不行，更小的数更不行，所以 r 必须跳到 mid - 1。很多同学会误以为 check(mid) 为真时应该让 r = mid，这是把‘可行’和‘最小可行’混淆了。因此，④处应填 A（r = mid - 1），⑤处应填 D（l = mid + 1）。

最后，关于考频与趋势：根据历年真题统计，‘二分答案 + 贪心’是信息学竞赛中的高频考点，尤其在 CSP-J/S 和 NOIP 的模拟赛中，这类题目几乎每年必出，且难度适中，属于‘拿分利器’。2021 年前后，这类题型在模拟赛中的出现频率约为 15%-20%，在正式比赛中约为 10%-12%。从趋势来看，命题人越来越喜欢将二分与贪心结合，考察学生对‘单调性’和‘可验证性’的深刻理解。未来几年，这类题目仍将是重点，但可能会在数据规模或附加条件上做微调，例如引入装备之间的依赖关系或动态变化，以增加区分度。

综上所述，本题的解题主线非常清晰：排序定贪心策略，二分定答案范围，check 函数验证可行性。只要抓住这几个关键点，避开下标错位和循环条件陷阱，就能稳稳拿下这道题。