#12306. 珅泽教育CSP-J第一轮模拟考第二十五套 第 34 题

珅泽教育CSP-J第一轮模拟考第二十五套 第 34 题

三、完善程序(程序一:装备穿戴问题)

nn 件装备,穿戴第 ii 件装备需要玩家的力量值至少为 aia_i,穿戴后力量值增加 bib_i。求能够以某种顺序穿戴全部装备所需的最小初始力量值。

输入第一行为整数 n(1n103)n (1\le n\le 10^3);第二行有 nn 个整数 ai(0ai109)a_i (0\le a_i\le 10^9);第三行有 nn 个整数 bi(0bi106)b_i (0\le b_i\le 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. ①处应填( )。

{{ select(1) }}

  • a[x] > a[y]
  • a[x] < a[y]
  • a[x] >= a[y]
  • a[x] <= a[y]