装备穿戴问题【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;
}