正经题解｜夺宝升级

题目解析

$n$ 个谜题，每个谜题 $i$ 挑战成功需要当前等级至少为 $a_i (1 \le i \le n)$ ，挑战成功即可将当前等级提升 $b_i (1 \le i \le 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$ 从小到大排序时间复杂度为 $O(n\log{n})$。