(装备穿戴问题)有 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处应填( )。
a[x] > a[y]
a[x] < a[y]
a[x] >= a[y]
a[x] <= a[y]
2处应填( )。
x < a[i]
x<a[u]
x >= a[i]
x>=a[u]
3处应填( )。
l<r
l<=r
check(l)
check(r)
4处应填( )。
r = mid – 1
r=mid+ 1
l = mid – 1
l=mid+ 1
5处应填( )。
r = mid – 1
r=mid+ 1
l = mid – 1
l=mid+ 1