C. Quests - 题解

比赛与标签

比赛: Codeforces Round 916 (Div. 3) 标签: greedy, math 难度: *1100

喵喵，题目讲了什么呀？

主人你好呀~ 这道题是关于一个游戏角色的升级任务哦！

我们有 n 个任务，编号从 1 到 n。为了升级，我们最多可以完成 k 次任务。

任务的规则有点特别呐：

任务1是随时都可以做的。
要解锁任务 i，我们必须先把所有编号小于 i 的任务（也就是 1, 2, ..., i-1）都至少完成过一次才行。
同一个任务可以重复完成很多次哦！

每次完成任务都能拿到经验值：

第一次完成任务 i，获得 a_i 点经验。
之后再完成任务 i，每次都获得 b_i 点经验。

我们的目标是，在总共不超过 k 次任务完成次数的限制下，获得最多的总经验值！该怎么安排才能拿到最多奖励呢，喵~？

解题思路大揭秘喵~

这道题看起来选择很多，但其实有一个关键的限制，就是任务必须按顺序解锁，不能跳着来！这给了我们一个非常清晰的思考方向，的说。

我们的核心决策是：我们到底要解锁多少个任务呢？

假设我们决定解锁前 p 个任务（从任务1到任务p）。

解锁成本：要解锁这 p 个任务，我们必须把它们各自都完成至少一次。这就要用掉 p 次完成机会。所以，我们必须保证 p <= k 才行哦。
解锁收益：完成这 p 个任务的第一次，我们获得的经验总和就是 a_1 + a_2 + ... + a_p。
剩余机会：在用掉 p 次机会解锁后，我们还剩下 k - p 次完成任务的机会。
贪心选择：现在，我们有 k - p 次机会，可以用来重复刷已经解锁的这 p 个任务中的任意一个。为了让经验最大化，我们当然要选择那个“重复收益”最高的任务啦！也就是在 b_1, b_2, ..., b_p 中找到那个最大的值，然后把所有 k - p 次机会都用在它身上，喵~ 这样最划算了！

所以，对于一个确定的 p，我们能获得的总经验就是： 总经验 = (a_1 + ... + a_p) + (k - p) * (b_1 到 b_p 中的最大值)

既然我们知道了如何计算解锁 p 个任务时的最大收益，那最终的答案就是尝试所有可能的 p，然后取其中的最大值！

p 可以从 1（只解锁任务1）一直到 min(n, k)（最多解锁 n 个任务，且解锁成本不能超过 k）。

我们可以写一个循环，遍历 p 从 1 到 min(n, k)。在循环中，我们动态地维护两个值：

current_sum_a: 当前解锁任务的 a_i 值总和。
current_max_b: 当前解锁任务中最大的 b_i 值。

当 p 增加 1 时，我们只需要把新的 a_p 加到 current_sum_a 上，并用新的 b_p 更新 current_max_b。这样每次计算都是 O(1) 的，非常快！整个算法的效率就非常高啦，的说！

代码实现时间到！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    std::vector<int> b(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; ++i) {
        std::cin >> b[i];
    }

    long long max_experience = 0;
    long long current_sum_a = 0;
    int current_max_b = 0;

    // 我们遍历决定要解锁的独特任务数量，喵~
    // 假设我们解锁前 'p' 个任务，这需要 'p' 次完成。
    // 这只有在 k >= p 的情况下才可能。
    // 循环变量 'i' 代表我们解锁的最后一个任务的索引（0-based）。
    // 所以，解锁的任务数 p = i + 1。
    // 循环的范围是从 p=1 到 min(n, k)。
    for (int i = 0; i < std::min(n, k); ++i) {
        // 累加前 i+1 个任务的首次完成奖励 a_i
        current_sum_a += a[i];
        
        // 在已解锁的前 i+1 个任务中，找到最大的重复奖励 b_i
        current_max_b = std::max(current_max_b, b[i]);
        
        // 到目前为止解锁的任务数量
        long long p = i + 1;
        
        // 解锁后，我们还剩下多少次完成机会
        long long remaining_k = k - p;
        
        // 计算当前策略下的总经验值：
        // 1. 首次完成所有已解锁任务的经验 (current_sum_a)
        // 2. 将剩余次数全部用于刷重复奖励最高的那个任务
        long long current_experience = current_sum_a + remaining_k * current_max_b;
        
        // 更新我们找到的全局最大经验值
        max_experience = std::max(max_experience, current_experience);
    }

    std::cout << max_experience << std::endl;
}

int main() {
    // 加速一下输入输出，让程序跑得飞快~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析喵

时间复杂度: O(min(n, k)) 的说。我们的主循环最多执行 min(n, k) 次。在循环的每一步，我们只做了几次加法、比较和乘法，这些都是 O(1) 的常数时间操作。所以总的时间复杂度就是由循环次数决定的呐。
空间复杂度: O(n) 的说。我们主要需要空间来存储输入的 a 和 b 两个数组，每个数组的大小都是 n。所以空间复杂度是 O(n)。

猫娘的小总结

这道题真有趣，不是吗？它教会了我们几件重要的事情哦：

识别关键决策点: 解决问题的突破口在于发现“解锁多少个任务”是我们可以枚举的核心决策。一旦这个决策定下来，剩下的就变成了简单的贪心问题。
贪心策略的应用: 对于剩余的 k-p 次机会，毫不犹豫地选择收益最高的 b_i 进行重复，这是典型的贪心思想，而且在这里是正确的！
动态维护（前缀思想）: 在循环中，我们没有傻傻地每次都重新计算 a 的总和与 b 的最大值。而是使用了 current_sum_a 和 current_max_b 来动态更新，这是一种类似“前缀和”与“前缀最大值”的思想，是优化循环效率的常用技巧，主人要记住哦！
注意边界: 循环的上限是 min(n, k)，这个小细节很关键。我们不能解锁比 n 更多的任务，也不能用超过 k 次的机会去解锁。

希望本猫娘的讲解对你有帮助！继续加油，享受解题的乐趣吧，喵~！

C. Quests - 题解 ​

比赛与标签 ​

喵喵，题目讲了什么呀？ ​

解题思路大揭秘喵~ ​

代码实现时间到！ ​

复杂度分析喵 ​

猫娘的小总结 ​