D. Lonely Mountain Dungeons - 题解

比赛与标签

比赛: Codeforces Round 924 (Div. 2) 标签: brute force, data structures, greedy, math, ternary search 难度: *1900

喵喵的题目大意！

喵哈喽~！各位寻宝的勇士们！为了夺回被恶龙史矛革抢走的宝藏，我们必须组建一支最强大的军队，的说！(ง •̀_•́)ง

是这样的，我们有 n 个不同的种族，每个种族有 c_i 个小勇士。我们可以把他们分成 k 个小队。军队的战斗力是这样计算的：

同族加成：对于同一个种族的两个小勇士，如果他们被分在不同的小队里，他们之间就会产生默契，为军队增加 b 点战斗力。
指挥惩罚：小队数量 k 太多的话，指挥官提摩西会很头大，所以每增加一个小队，总战斗力就会减少 x 点。也就是说，k 个小队会产生 (k-1) * x 的惩罚。

我们的任务就是，决定到底要分多少个小队（也就是决定 k 的值），以及如何分配每个种族的成员，来让最终的战斗力达到最大值，喵~！

解题思路：像猫咪一样思考！🐾

这道题的核心就是找到最优的小队数量 k，呐。最终的战斗力公式是：总加成 - 总惩罚。

总加成 = (所有在不同小队的同族勇士对数) * b总惩罚 = (k - 1) * x

看起来有点复杂，我们一步一步来拆解！

第一步：如何分配勇士？

假设我们已经决定要组建 k 个小队。对于某个拥有 c 个勇士的种族，要怎样分配他们才能让“在不同小队的勇士对数”最多呢？

这其实等价于一个反向的问题：如何让“在相同小队的勇士对数”最少！

想象一下，你有 c 个猫抓板，要分到 k 个猫窝里。为了让每个猫窝里的猫抓板数量尽可能平均，我们会怎么做呢？当然是均匀地分啦！

所以，最优策略就是把 c 个勇士 尽可能均匀地 分配到 k 个小队里。具体来说，c 除以 k 的商是 q，余数是 r (c = q*k + r)。那么，我们就让 r 个小队分配 q+1 个勇士，剩下的 k-r 个小队分配 q 个勇士。这样分配能保证在同一小队内的勇士对数最少，从而使不同小队间的勇士对数最多！

第二步：如何确定 `k` 的范围？

我们可以尝试所有可能的 k 值，然后计算出每个 k 对应的最大战斗力，最后取其中的最大值。但 k 的范围是多大呢？

如果 k 比任何一个种族的勇士数量 c_i 都要大，比如说 k > max(c_i)，那么对于任何一个种族，我们都可以把它的每个勇士都分到不同的小队里。此时再增加 k 的值，并不能产生更多的“不同小队勇士对”，反而会增加 (k-1)*x 的惩罚。这显然不划算，的说！

所以，我们只需要枚举 k 从 1 到所有 c_i 中的最大值 c_max 就足够了。

第三步：如何快速计算战斗力？(ฅ^•ﻌ•^ฅ)

我们现在需要对每个 k（从 1 到 c_max）计算总战斗力。如果对每个 k 都遍历一遍所有 n 个种族来计算，复杂度会是 O(n * c_max)，这太慢了，会超时的喵！

我们需要一个更快的计算方法。

总战斗力 S(k) = (所有种族贡献的总对数) * b - (k - 1) * x

一个种族内部的总勇士对数是 c * (c - 1) / 2，这是个固定的值。我们设所有种族内部的总对数之和为 TotalPairs。设 g(c, k) 为一个有 c 个勇士的种族，在分成 k 个小队时，在相同小队 的勇士对数。那么 S(k) = (TotalPairs - sum(g(c_i, k))) * b - (k-1) * x。

为了最大化 S(k)，我们需要计算 sum(g(c_i, k))。经过一番推导（这里的小魔法有点复杂，可以记住结论~），我们可以得到一个漂亮的公式： g(c, k) = c*q - k*q*(q+1)/2，其中 q = floor(c/k)。

现在，对于一个固定的 k，我们需要计算 G_k = sum(g(c_i, k))。直接遍历所有 c_i 还是慢。但我们发现 g(c, k) 的值主要由 q = floor(c/k) 决定。所以，我们可以把所有种族按照 q = floor(c_i/k) 的值进行分组！

优化大作战！

预处理：我们先统计一下，勇士数量为 v 的种族有多少个，记在 counts[v] 数组里。然后用前缀和预处理出 p_counts (数量的前缀和) 和 p_c_sums (勇士总数的前缀和 c*counts[c] 的前缀和)。
高效计算 G_k：对于固定的 k，我们不遍历 c_i，而是遍历 q (从 0 开始)。
- 对于每个 q，所有满足 floor(c_i/k) = q 的 c_i 都落在区间 [q*k, (q+1)*k - 1] 内。
- 我们可以用前缀和，瞬间（O(1)）查出这个区间内有多少个种族 (num_races)，以及这些种族的勇士总数是多少 (sum_c_for_q)。
- 这一组种族对 G_k 的贡献就是 sum(c_i*q - k*q*(q+1)/2) = q*sum(c_i) - num_races*k*q*(q+1)/2。
- 把所有 q 的贡献加起来，就得到了 G_k。

这个计算 G_k 的过程，对于一个 k，需要遍历 q，而 q 的最大值是 c_max / k。所以总的计算量是 sum_{k=1}^{c_max} (c_max / k)，约等于 O(c_max * log(c_max))，这就非常快啦！

总结一下我们的计划：

预处理，统计每个勇士数量 c 出现的次数，并计算前缀和。
计算出所有种族内部的总对数 TotalPairs。
遍历 k 从 1 到 c_max。
对于每个 k，使用分组和前缀和的方法，快速计算出在相同小队内的总对数 G_k。
计算当前 k 下的总战斗力 (TotalPairs - G_k) * b - (k - 1) * x。
在所有 k 的结果中，取最大值，就是我们的答案啦！

代码实现：看我的喵喵拳！

cpp

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

void solve() {
    int n;
    long long b, x;
    std::cin >> n >> b >> x;
    std::vector<int> c(n);
    int c_max = 0;
    for (int i = 0; i < n; ++i) {
        std::cin >> c[i];
        c_max = std::max(c_max, c[i]);
    }

    // 如果没有勇士，战斗力就是0啦
    if (c_max == 0) {
        std::cout << 0 << "\n";
        return;
    }

    // counts[i] 记录勇士数量为 i 的种族有多少个
    std::vector<long long> counts(c_max + 1, 0);
    for (int val : c) {
        counts[val]++;
    }

    // p_counts[i] 是 counts 的前缀和，p_c_sums[i] 是 c_i * counts[c_i] 的前缀和
    // 这两个数组是我们快速计算的关键！喵~
    std::vector<long long> p_counts(c_max + 1, 0);
    std::vector<long long> p_c_sums(c_max + 1, 0);
    for (int i = 1; i <= c_max; ++i) {
        p_counts[i] = p_counts[i - 1] + counts[i];
        p_c_sums[i] = p_c_sums[i - 1] + counts[i] * i;
    }

    // 计算所有种族内部的总对数，这是一个固定值
    long long total_pairs_val = 0;
    for (int i = 1; i <= c_max; ++i) {
        if (counts[i] > 0) {
            total_pairs_val += counts[i] * (long long)i * (i - 1) / 2;
        }
    }

    long long max_strength = 0;

    // 枚举小队数量 k 从 1 到 c_max
    for (int k = 1; k <= c_max; ++k) {
        // G_k 表示在 k 个小队时，所有在相同小队内的勇士对数总和
        long long G_k = 0; 
        
        // 按照 q = floor(c/k) 的值来分组计算
        for (long long q = 0; ; ++q) {
            long long L = q * k;
            if (L > c_max) {
                break;
            }
            long long R = (q + 1) * k - 1;
            R = std::min(R, (long long)c_max);

            // 使用前缀和快速查找区间 [L, R] 内的种族数量
            long long num_races = p_counts[R] - (L > 0 ? p_counts[L - 1] : 0);
            if (num_races == 0) {
                continue;
            }

            // 使用前缀和快速查找区间 [L, R] 内的勇士总数
            long long sum_c_for_q = p_c_sums[R] - (L > 0 ? p_c_sums[L - 1] : 0);
            
            // 这是我们推导出的魔法公式 g(c,k) = c*q - k*q*(q+1)/2 的求和版本
            // 对一个q值的所有种族，它们对 G_k 的总贡献
            G_k += sum_c_for_q * q - num_races * k * q * (q + 1) / 2;
        }
        
        // 在不同小队的对数 = 总对数 - 在相同小队的对数
        long long F_k = total_pairs_val - G_k; 
        long long current_strength = F_k * b - (long long)(k - 1) * x;
        max_strength = std::max(max_strength, current_strength);
    }

    std::cout << max_strength << "\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(C_max * log(C_max)) 的说。这里的 C_max 是勇士数量的最大值。外层循环从 k=1 到 C_max，内层循环对 q 的迭代次数是 C_max / k。总的迭代次数是 sum(C_max / k) for k from 1 to C_max，这等于 C_max * H(C_max)，其中 H 是调和级数，约等于 log(C_max)。所以总时间复杂度就是 O(C_max * log(C_max))，非常高效！
空间复杂度: O(C_max) 的说。我们主要使用了 counts, p_counts, p_c_sums 这几个数组来存储信息，它们的大小都和 C_max 成正比。

知识点与总结：今天学到了什么喵~

这道题真有趣，不是吗？它完美地融合了好几种思想：

贪心策略: 对于固定的 k，我们贪心地选择最均匀的分配方式来最小化内部矛盾（相同小队内的对数）。
数学推导: 我们通过数学推导找到了计算 g(c, k) 的简洁公式，这是从暴力解法迈向高效解法的关键一步！
枚举与优化: 我们确定了枚举 k 的有效范围，并用 “按商分组 + 前缀和” 的技巧，将原本 O(n * C_max) 的暴力枚举优化到了 O(C_max * log(C_max))。
数据结构: 前缀和真是个好东西！它能让我们把区间查询从 O(N) 降到 O(1)，是许多优化问题的得力助手，的说。

所以，解决一个复杂问题，往往需要我们先看清问题的本质（贪心），然后用数学工具简化它，最后再用巧妙的数据结构和算法来加速计算。多做这样的题目，你的思维也会像猫咪一样越来越敏捷的！加油，喵~！

D. Lonely Mountain Dungeons - 题解 ​

比赛与标签 ​

喵喵的题目大意！ ​

解题思路：像猫咪一样思考！🐾 ​

第一步：如何分配勇士？ ​

第二步：如何确定 k 的范围？ ​

第三步：如何快速计算战斗力？(ฅ^•ﻌ•^ฅ) ​

总结一下我们的计划： ​

代码实现：看我的喵喵拳！ ​

复杂度分析：我们出击有多快？ ​

知识点与总结：今天学到了什么喵~ ​