Moe's CF Life

Appearance

F. Quests - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 835 (Div. 4) 标签: binary search, greedy, sortings 难度: *1500

题目大意喵~ ​

主人你好呀~ 这道题是这样的：我们有 n 个任务可以做，每个任务 i 完成后能拿到 a_i 个金币。我们总共有 d 天的时间，每天最多只能完成一个任务。

这里有一个特殊的规则哦：如果我们完成了一个任务，那么在接下来的 k 天里都不能再做这个任务了。举个例子，如果 k=2，我们在第1天做了任务1，那么第2天和第3天就不能再做它了，直到第4天才能再次选择任务1。

我们的目标是，在 d 天内赚到至少 c 个金币。题目想让我们找到一个最大的整数 k，使得这个目标能够实现。

有几种特殊情况需要注意呐：

  • 如果无论 k 是多少，我们都无法赚够 c 个金币，就输出 Impossible。
  • 如果 k 可以是任意大的正整数（比如我们第一天就赚够了钱，后面根本不需要再做任务），就输出 Infinity。
  • 否则，就输出那个最大的 k 啦！

解题思路大解析！ ​

这道题看起来有点复杂，但别担心，我们一步一步来拆解它，喵~

第一步：贪心是最好的策略喵！ ​

要想在 d 天内赚尽可能多的金币，我们肯定希望每天都做当前能做的、奖励最高的任务，对吧？这是一个非常直观的贪心思路。所以，我们第一步要做的就是把所有任务的奖励 a_i 从大到小排个序。这样，我们手里就有了一个按奖励排序的任务列表，随时可以从中挑选最好的任务啦！

第二步：特殊情况要先处理好哦~ ​

在开始复杂的计算之前，我们先把两个最简单的情况处理掉：

  1. "Impossible" 的情况：我们能赚到的金币最多是什么情况呢？当然是 k=0 的时候啦！k=0 意味着没有任何冷却时间，我们可以每天都做那个奖励最高的任务（就是排序后的 a[0]）。如果在这种最理想的情况下，d 天内赚到的金币 a[0] * d 都比 c 少，那肯定是永远也达不成目标的。所以，如果 a[0] * d < c，直接输出 Impossible 就好啦。

  2. "Infinity" 的情况：什么时候 k 可以无限大呢？就是当我们根本不需要重复做任何任务的时候。如果我们只用前 d 天（如果任务总数 n 比 d 小，那就是前 n 天），每天做一个不同的、奖励最高的任务，就已经能赚够 c 个金币了，那之后就不用再管什么冷却时间了，k 可以随便设多大都行。所以，我们计算一下前 min(n, d) 个奖励最高的任务的总和，如果这个总和大于等于 c，就可以自信地输出 Infinity 啦！

第三步：发现单调性，二分出击！ ​

处理完特殊情况，剩下的就是寻找最大的那个 k 了。我们来观察一下 k 的性质：

假设一个 k 值是可行的（我们能用它赚够 c 个金币）。那么，一个比它更小的 k'（比如 k-1）是不是也一定可行呢？答案是肯定的！因为更小的 k 意味着任务的冷却时间更短，我们能更频繁地做那些高奖励的任务，赚到的钱只会多不会少。

这种 “如果 k 可行，那么所有小于 k 的值也都可行” 的性质，就是单调性！一看到这种性质，我们聪明的脑袋里就应该亮起一盏灯：二分答案！

我们可以对 k 进行二分查找。k 的取值范围可以是 0 到 d（k 比 d 大没有意义，因为在 d 天内根本不会重复任务）。我们来设计一个 check(k) 函数，它用来判断对于给定的 k，我们最多能赚多少金币，看是否能达到 c。

第四步：check(k) 函数的设计喵~ ​

check(k) 函数是二分搜索的核心。对于一个给定的 k，我们来算算 d 天内最多能赚多少钱。

  • 任务的冷却周期是 k+1 天。也就是说，我们可以在 k+1 天里，每天做一个不同的任务。根据贪心策略，我们肯定会选择奖励最高的前 k+1 个任务来轮流做。
  • 在 d 天里，我们可以完成 d / (k+1) 个完整的周期。
  • 每个完整周期，我们都会把前 k+1 个奖励最高的任务做一遍。
  • 完成这些完整周期后，还剩下 d % (k+1) 天。在这几天里，我们同样会贪心地选择奖励最高的前 d % (k+1) 个任务来做。

为了快速计算这些任务奖励的和，我们可以预处理一个前缀和数组 pref。pref[i] 存的是排序后前 i 个任务的奖励总和。这样，我们就能在 O(1) 的时间内算出任意前 x 个任务的和啦！

所以，对于一个 k：

  • 一个周期的收益是 pref[k+1]。（如果 k+1 > n，那就只能做完所有 n 个任务，收益是 pref[n]）。
  • d 天的总收益就是 (d / (k+1)) * (一个周期的收益) + pref[d % (k+1)]。

我们用这个总收益和 c 比较，就可以知道当前的 k 是否可行了。

二分搜索的逻辑： ​

  • 我们在 [0, d+1] 这个范围里二分查找 k。
  • mid = low + (high - low) / 2。
  • 如果 check(mid) 返回 true（意味着用 mid 作为冷却天数可以赚够钱），说明 mid 是一个可能的答案，我们还想试试看有没有更大的 k 也行，所以我们记录下 mid，然后让 low = mid + 1。
  • 如果 check(mid) 返回 false，说明 mid 太大了，冷却时间太长导致赚不够钱，我们需要减小 k，所以让 high = mid - 1。

最后，我们记录下的那个最大的可行 k 就是答案啦！

代码实现喵~ ​

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

void solve() {
    long long n, c, d;
    std::cin >> n >> c >> d;
    std::vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
    
    // 贪心第一步：将任务奖励从大到小排序，喵~
    std::sort(a.rbegin(), a.rend());
    
    // 特殊情况1：不可能完成。
    // 如果每天都做奖励最高的任务，d天都凑不够c，那就真的没办法了。
    if (a[0] * d < c) {
        std::cout << "Impossible\n";
        return;
    }
    
    // 特殊情况2：k可以无限大。
    // 如果只用前 min(n, d) 个不同的高奖励任务就能凑够c，那就不需要重复任务，k可以任意大。
    long long sum_first_d = 0;
    for (long long i = 0; i < std::min(n, d); ++i) {
        sum_first_d += a[i];
    }
    if (sum_first_d >= c) {
        std::cout << "Infinity\n";
        return;
    }
    
    // 为了快速计算收益，我们预处理前缀和数组 pref
    std::vector<long long> pref(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        pref[i + 1] = pref[i] + a[i];
    }
    
    // 开始二分查找 k 的最大值！
    long long low = 0, high = d + 1, ans = 0;
    while (low <= high) {
        long long k = low + (high - low) / 2;
        
        // 一个完整的任务周期是 k+1 天
        long long k_plus_1 = k + 1;
        
        // 计算 d 天内有多少个完整的周期
        long long num_cycles = d / k_plus_1;
        // 计算完整周期后还剩多少天
        long long rem_days = d % k_plus_1;
        
        long long total_coins;
        
        // 计算总金币数，注意如果 k+1 > n，一个周期只能做 n 个任务
        if (k_plus_1 <= n) {
            // 完整周期的收益 + 剩余天数的收益
            total_coins = num_cycles * pref[k_plus_1] + pref[rem_days];
        } else {
            // 任务数不够一个周期，每个周期都是做完所有n个任务
            total_coins = num_cycles * pref[n] + pref[std::min(n, rem_days)];
        }
        
        // check(k) 的判断
        if (total_coins >= c) {
            // 这个 k 可行，我们把它存下来，然后尝试更大的 k
            ans = k;
            low = k + 1;
        } else {
            // 这个 k 不行，太大了，需要减小 k
            high = k - 1;
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析 ​

  • 时间复杂度: O(n log n + log d) 的说。

    • 对于每个测试用例，我们首先需要对 n 个任务奖励进行排序，这需要 O(n log n) 的时间。
    • 之后我们计算前缀和，需要 O(n) 的时间。
    • 核心的二分查找部分，搜索范围是 [0, d+1]，所以会进行 O(log d) 次迭代。在每次迭代中，check 函数的计算因为有了前缀和，只需要 O(1) 的时间。
    • 所以总的时间复杂度是 O(n log n + log d) 呐。

  • 空间复杂度: O(n) 的说。

    • 我们需要一个数组 a 来存储 n 个任务的奖励，还需要一个前缀和数组 pref，大小也是 n+1。所以空间复杂度是 O(n)。

知识点与总结 ​

这道题是一道非常经典的 “贪心 + 二分答案” 组合题，喵~

  1. 贪心策略 (Greedy)：遇到求最优解的问题，首先可以想想有没有简单的贪心策略。在这里，“总是选择当前可用的、奖励最高的任务” 就是一个非常有效的贪心策略，它为我们后续的计算奠定了基础。

  2. 二分答案 (Binary Search on Answer)：当题目要求解一个最大（或最小）值，并且这个值的可行性具有单调性时，二分答案就是我们的不二之选！识别出单调性是解决这类问题的关键。

  3. 前缀和优化 (Prefix Sum)：在二分的 check 函数中，如果需要反复求一个区间的和，预处理前缀和数组是一种非常常见的优化技巧，能将求和的时间从 O(n) 降到 O(1)。

  4. 边界处理 (Edge Cases)：像 Impossible 和 Infinity 这样的特殊情况，在主逻辑开始前单独处理，可以让代码结构更清晰，也能避免在二分过程中出现意想不到的错误。

希望这篇题解能帮助到你，一起加油，成为更厉害的算法大师吧，喵~！

Released under the MIT License.

Copyright © 2024-present Moe