2296 . 综合题

装备穿戴问题【SCP 2021 第一轮(初赛)模拟】

有 $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 <= n; ++i) scanf("%d", b + i);
    for (int i = 1; i <= n; ++i) c[i] = i;
    sort(c + 1, c + 1 + n, Comp);
    int ans = 1145141919;
    for (int l=1, r=ans, mid=(l+r)/2; ③; mid=(l+r)/2)
        if (check(mid)) {
            ans = mid;
            ④;
        } else {
            ⑤;
        }
    printf("%d\n", ans);
    return 0;
}
1 . (单选题)

① 处应填( )

2 . (单选题)

② 处应填( )

3 . (单选题)

③ 处应填( )

4 . (单选题)

④ 处应填( )

5 . (单选题)

⑤ 处应填( )