F - For the Treasury! - 题解

标签与难度

标签: 贪心, 数学, 排序, 贡献法, 思维题 难度: 1600

题目大意喵~

各位寻宝家们，晚上好喵~！我们来帮助聪明的维京首领 Askeladd 解决一个财富最大化的问题吧，嘻嘻~

事情是这样的：Askeladd 和他的伙伴们找到了 n 个宝藏，排成一排，每个宝藏都有自己的价值 a_i。按照约定，作为首领的 Askeladd 可以拿走排在最前面的 k 个宝藏。

不过呢，Askeladd 是个狡猾的家伙！他想在夜深人静的时候，通过交换相邻宝藏的方式，把更有价值的宝藏移动到前 k 个位置。但是，每次交换都会有 c 的成本，因为有被发现的风险嘛。

我们的任务就是，帮 Askeladd 计算一下，他通过任意次交换后，能得到的最大利润是多少。 最大利润 = (他拿走的 k 个宝藏的总价值) - (所有交换的总成本)。

解题思路分析

这道题看起来有点复杂呢，要把哪个宝藏换到前面，换多少次，好像有无数种可能，让人头晕眼花，喵~ 但别担心，跟着我的思路，一步步就能解开谜题！

1. 问题的核心是什么？

我们的目标是选择 k 个宝藏，并将它们移动到序列的前 k 个位置，同时让最终的“价值 - 成本”最大化。

2. 成本如何计算？

一个关键的事实是：把一个位于初始位置 i 的宝藏，通过只交换相邻元素的方式，移动到位置 j，最少需要 |i - j| 次交换。所以成本就是 c * |i - j|。

3. 一个简单的想法：贪心交换

让我们来考虑一个简单的情况。假设我们已经有了一组在前 k 个位置的宝藏，以及另一组在 k 个位置之后的宝藏。我们什么时候会想把一个靠后的宝藏 a_j (初始在 j 位置, j > k) 和一个靠前的宝藏 a_i (初始在 i 位置, i <= k) 交换呢？

如果我们把 a_j 换到 a_i 的位置，我们需要进行 j - i 次交换，成本是 c * (j - i)。而我们获得的价值增加了 a_j - a_i。 这次“宏观”交换带来的利润变化是：(a_j - a_i) - c * (j - i)。

我们当然希望这个利润变化是正的，也就是说，只有当 (a_j - a_i) - c * (j - i) > 0 时，这次交换才划算。 我们把这个不等式变形一下，喵~ a_j - c * j > a_i - c * i

4. 发现新大陆！

看呐！这个不等式告诉我们一个惊人的秘密！一个宝藏是否“优秀”，不仅仅取决于它的价值 a_p，还和它的初始位置 p 有关。我们可以定义一个全新的评估标准，叫做“潜力值”，potential(p) = a_p - c * p。

刚才的结论就变成了：只要一个靠后的宝藏 j 的潜力值 potential(j) 大于一个靠前宝藏 i 的潜力值 potential(i)，把它们交换就是有利可图的！

这启发我们，最终被 Askeladd 收入囊中的那 k 个宝藏，一定是所有 n 个宝藏中，潜力值最大的那 k 个！这，就是我们需要的贪心策略，喵！

5. 计算最终利润

好啦，我们现在知道该选哪 k 个宝藏了。假设我们选出的 k 个宝藏的初始位置是 p_1, p_2, ..., p_k（并且我们已经按大小排好序，p_1 < p_2 < ... < p_k）。

为了让移动成本最小，我们应该保持这 k 个宝藏的相对顺序不变。也就是说，把初始在 p_1 的宝藏移动到最终的 1 号位，p_2 的移到 2 号位，...，p_k 的移到 k 号位。

• 总价值 = a_{p_1} + a_{p_2} + ... + a_{p_k}
• 总成本 = c*(p_1-1) + c*(p_2-2) + ... + c*(p_k-k)

所以，最大利润 Profit 就是： Profit = (a_{p_1} + ... + a_{p_k}) - (c*(p_1-1) + ... + c*(p_k-k))

让我们再次施展数学魔法，整理一下这个公式： Profit = (a_{p_1} - c*p_1 + c*1) + (a_{p_2} - c*p_2 + c*2) + ... + (a_{p_k} - c*p_k + c*k)Profit = ( (a_{p_1} - c*p_1) + ... + (a_{p_k} - c*p_k) ) + (c*1 + c*2 + ... + c*k)Profit = (我们选出的k个宝藏的潜力值之和) + c * (1 + 2 + ... + k)

哇！看，最终的利润可以分解成两部分：

1. 我们选出的 k 个宝藏的潜力值之和。
2. 一个固定的常数 c * (1 + 2 + ... + k)。这个求和是一个等差数列，等于 c * k * (k+1) / 2。

注意喵: 如果你像我一样，在代码里使用从 0 开始的下标（0-indexed），那么位置就变成了 0, 1, ..., k-1，那个常数项就变成了 c * (0 + 1 + ... + k-1) = c * k * (k-1) / 2。

6. 算法总结

所以，解题步骤就非常清晰啦：

1. 对于每个宝藏 i (从 0 到 n-1)，计算它的潜力值 potential_i = a_i - c * i。
2. 将所有 n 个潜力值从大到小排序。
3. 取出前 k 个最大的潜力值，将它们加起来。
4. 再加上那个神奇的常数 c * k * (k-1) / 2。
5. 得到的结果就是最大利润啦！

代码实现

下面是我根据这个思路，精心为你准备的代码哦~ 注释超详细的，快来看看吧！

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

// 为了代码的可读性，我们定义一些类型别名，喵~
using ll = long long;

int main() {
    // 使用 std::ios::sync_with_stdio(false) 和 cin.tie(nullptr) 可以加速输入输出，
    // 在处理大量数据时很有用哦！
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    ll k, c;
    std::cin >> n >> k >> c;

    // 如果 Askeladd 一个宝藏都不拿 (k=0)，那利润当然是 0 啦。
    if (k == 0) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // 创建一个 vector 来存储每个宝藏的“潜力值”。
    std::vector<ll> potentials(n);
    for (int i = 0; i < n; ++i) {
        ll val;
        std::cin >> val;
        // 计算潜力值：a_i - c * i (使用 0-indexed)
        // 注意 i 是 int 类型，c 可能是 long long，需要类型转换防止溢出。
        potentials[i] = val - c * i;
    }

    // 将潜力值从大到小排序。
    // std::sort 默认是升序，所以我们用 std::greater<ll>() 来实现降序。
    std::sort(potentials.begin(), potentials.end(), std::greater<ll>());

    // 计算前 k 个最大潜力值的和。
    ll sum_of_top_k_potentials = 0;
    for (int i = 0; i < k; ++i) {
        sum_of_top_k_potentials += potentials[i];
    }

    // 计算那个神奇的常数项。
    // 因为我们用的是 0-indexed，所以是 c * (0 + 1 + ... + k-1)
    // 公式是 c * k * (k-1) / 2
    ll constant_term = c * k * (k - 1) / 2;

    // 最终利润 = 潜力值之和 + 常数项
    ll max_profit = sum_of_top_k_potentials + constant_term;

    std::cout << max_profit << std::endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(N \log N)$ 主要的时间开销在于对 n 个潜力值进行排序，这需要 $O(N \log N)$ 的时间。计算潜力值和求和都只需要 $O(N)$ 和 $O(k)$ 的时间，所以排序是瓶颈。

• 空间复杂度: $O(N)$ 我们创建了一个大小为 n 的 potentials 向量来存储计算出的潜力值，所以需要 $O(N)$ 的额外空间。

知识点总结

这道题真有趣，不是吗？它完美地展示了如何用聪明的数学变换来简化一个看似复杂的问题，喵~

1. 贪心算法 (Greedy Algorithm): 问题的核心是找到了一个局部最优的判断标准 (a_j - c*j > a_i - c*i)，并证明了它能导向全局最优解。
2. 贡献法/潜力法 (Contribution Method): 我们没有直接去模拟复杂的交换过程，而是把成本 c*i 分摊到了每个物品上，创造了“潜力值”这个概念。这是解决许多贪心和动态规划问题时的强大武器！
3. 数学简化: 将复杂的利润公式通过代数变形，拆分成“变量部分”和“常量部分”，使得问题大大简化。这是算法竞赛中必备的数学思维，呐。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦~ 祝你刷题愉快，喵~！