题库 信息学奥赛题库 题目列表 (装备穿戴问题)有 n 件装备,穿戴第 i...
组合题

(装备穿戴问题)有 n 件装备,穿戴第 i 件装备需要玩家的力量值至少为 𝑎𝑖,穿戴该装备后会让玩家的力量值增加 𝑏𝑖。现在请问玩家的初始力量 值最小是多少,才能以某种顺序穿戴上所有的装备? 输入:第一行是一个整数 n(1 ≤ 𝑛 ≤ 103);第二行有 n 个整数,第 i 个 整数表示 𝑎𝑖(0 ≤ 𝑎𝑖 ≤ 109);第三行有 n 个整数,第 i 个整数表示 𝑏𝑖 ( 0 ≤ 𝑏 𝑖 ≤ 1 0 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 1;
}
bool check(int x) {
    for(int i = 1; i < =n; ++i){
    int u = c[i];
    if (2) {
        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; 3; mid=(l+r)/2)
        if (check(mid)) {
            ans = mid;
            4;
        } else {
            5;
        }
    printf("%d\n", ans);
    return 0;
}
第1题 单选

1处应填( )。

A.

a[x] > a[y]

B.

a[x] < a[y]

C.

a[x] >= a[y]

D.

a[x] <= a[y]

第2题 单选

2处应填( )。

A.

x < a[i]

B.

x<a[u]

C.

x >= a[i]

D.

x>=a[u]

第3题 单选

3处应填( )。

A.

l<r

B.

l<=r

C.

check(l)

D.

check(r)

第4题 单选

4处应填( )。

A.

r = mid – 1

B.

r=mid+ 1

C.

l = mid – 1

D.

l=mid+ 1

第5题 单选

5处应填( )。

A.

r = mid – 1

B.

r=mid+ 1

C.

l = mid – 1

D.

l=mid+ 1

题目信息
完善程序 2021年 练习
-
正确率
0
评论
296
点击