题目解析
n
n 个谜题，每个谜题
i
i 挑战成功需要当前等级至少为
a
i
(
1
≤
i
≤
n
)
a
i
(1≤i≤n) ，挑战成功即可将当前等级提升
b
i
(
1
≤
i
≤
n
)
b
i
(1≤i≤n)，谜题挑战的顺序不做限制。
那么显然我们可以按照谜题挑战需要的等级，从小到大挑战谜题。
AC代码
#include <bits/stdc++.h>
using namespace std;
int main() {
// cin, cout解绑加速输入输出
cin.tie(nullptr)->sync_with_stdio(false);
int _; cin >> ;
while (--) {
int n, k;
cin >> n >> k;
vector<int> a(n), b(n), id(n);
// 读入数组a和数组b
for (auto &x : a) cin >> x;
for (auto &x : b) cin >> x;
// id 数组初始化为 [0, 1, ... , n - 1]
iota(begin(id), end(id), 0);
// 使用 id 数组根据a[i]值从小到大进行排序
sort(begin(id), end(id), [&](const int &_a, const int &_b) {
return a[_a] < a[_b];
});
// 按照 a[i] 从小到大遍历谜题
for (auto &i : id) {
if (k < a[i]) break;
k += b[i];
}
cout << k << '\n';
}
return 0;
}
复杂度分析
将谜题按照
a
i
a
i
从小到大排序时间复杂度为
O
(
n
log
n
)
O(nlogn)。
