D. Array and Operations - 题解

比赛与标签

比赛: Codeforces Round 760 (Div. 3) 标签: dp, greedy, math 难度: *1300

题目大意喵~

主人，这道题目是这样子的：我们有一个长度为 n 的数组 a 和一个整数 k。我们需要精确地进行 k 次操作。

每次操作，我们要从数组里选出两个元素 a_i 和 a_j（它们的位置不能相同哦），把它们从数组中移除，然后将 floor(a_i / a_j) 的值加到我们的得分上。

在完成 k 次操作后，数组里还会剩下 n - 2k 个元素，我们要把这些剩下的所有元素也加到总得分里。

我们的目标是，通过巧妙地选择每次操作的元素，让最终的总得分变得最小最小~ 明白了吗，喵？

解题思路详解~

想要让总得分最小，我们就得好好分析一下得分的构成呐。总分 = (k 次除法操作的得分) + (剩下元素的和)。为了让这个总和最小，我们得让这两个部分都尽可能小才行，对吧？这是一个非常经典的贪心思路哦！

第一步：如何让剩下元素的和最小？

这简直太简单啦！要想让 n - 2k 个元素的和最小，我们当然应该留下数组中那 n - 2k 个最小的数呀！任何一个大一点的数留下来，都会让和变大，这可不是我们想要的。所以，第一步就是先把数组从小到大排个序，然后决定把最小的 n - 2k 个数留下来。它们的和就是我们得分的一部分啦。

第二步：如何让 k 次除法操作的得分最小？

好啦，现在我们用掉了最小的 n - 2k 个数，还剩下 2k 个最大的数。我们需要用这 2k 个数来进行 k 次 floor(分子 / 分母) 的操作。

要想让 floor(分子 / 分母) 的值最小，我们应该遵循一个简单的原则：让分子尽可能小，分母尽可能大。

现在我们手里有 2k 个已经排好序的、最大的数。我们可以把它们分成两组：

较小的一半：这 k 个数，我们应该把它们当作分子。
较大的一半：这 k 个数，我们应该把它们当作分母。

这样一来，我们就能保证每次都是用一个相对小的数去除以一个相对大的数，得到的商就很容易是 0 或者很小啦！

第三步：怎么配对分子和分母呢？

我们已经确定了哪 k 个数做分子，哪 k 个数做分母。那怎么配对才是最优的呢？假设排好序后，剩下的 2k 个数是 b_1, b_2, ..., b_{2k}。我们的分子就是 b_1, ..., b_k，分母就是 b_{k+1}, ..., b_{2k}。

最贪心的配对方法就是：最小的分子配对最小的分母，第二小的分子配对第二小的分母，以此类推。也就是用 b_i 去除以 b_{k+i}。

为什么这样最好呢？因为 b_i 总是小于 b_{k+i} 的，这样配对可以最大化 floor(b_i / b_{k+i}) 结果为 0 的次数。任何其他的配对方式（比如用最小的分子去除以最大的分母）都可能让某个较大的分子配上一个较小的分母，从而导致商变大，总分就不是最小了哦。

总结一下我们的策略喵：

将整个数组 a 从小到大排序。
最小的 n - 2k 个元素 (a[0] 到 a[n-2k-1]) 不参与除法操作，直接将它们的值加入总分。
接下来的 k 个元素 (a[n-2k] 到 a[n-k-1]) 作为分子。
最大的 k 个元素 (a[n-k] 到 a[n-1]) 作为分母。
将第 i 个分子 (a[n-2k+i]) 和第 i 个分母 (a[n-k+i]) 配对，计算 a[n-2k+i] / a[n-k+i] (在C++中整除就是下取整啦)，并加入总分。

这样，我们就能得到最小的总分啦，是不是很简单呢，喵~

代码实现喵~

cpp

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

// Function to solve a single test case
void solve() {
    int n;
    int k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 为了实施我们的贪心策略，第一步就是排序！
    // 这样我们就能轻松找到最小和最大的元素了，喵~
    std::sort(a.begin(), a.end());

    long long score = 0;

    // 1. 首先，我们把 n - 2k 个最小的元素直接加到分数里。
    //    因为它们不参与除法运算，为了总分最小，当然是留下值最小的那些啦。
    //    这些元素在排好序的数组里，就是下标从 0 到 n - 2*k - 1 的部分。
    //    这个循环很聪明，如果 k=0，它会把所有元素都加起来，完全正确！
    for (int i = 0; i < n - 2 * k; ++i) {
        score += a[i];
    }

    // 2. 接下来，我们处理剩下的 2k 个最大的元素，用它们进行 k 次除法操作。
    //    为了让除法结果之和最小，我们用这 2k 个数中较小的那 k 个做分子，
    //    较大的那 k 个做分母。
    //    分子是: a[n-2k] ... a[n-k-1]
    //    分母是: a[n-k] ... a[n-1]
    //
    // 3. 我们把第 i 小的分子和第 i 小的分母配对，这样能最大化得到 0 的机会。
    //    这个循环在 k=0 时不会执行，也是对的哦。
    for (int i = 0; i < k; ++i) {
        // 第 i 个分子的下标
        int numerator_idx = n - 2 * k + i;
        // 第 i 个分母的下标
        int denominator_idx = n - k + i;
        
        // 对于正整数，C++的整除 `/` 效果和 floor 函数是一样的，很方便！
        score += a[numerator_idx] / a[denominator_idx];
    }

    std::cout << score << 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(n log n) 的说。整个算法最耗时的部分就是对数组 a 进行排序，它的时间复杂度是 O(n log n) 呐。后面的两个循环都是线性的，最多遍历 n 个元素，所以总的时间复杂度由排序决定。
空间复杂度: O(n) 的说。我们主要用了一个 vector 来存储输入的 n 个整数，所以空间复杂度和输入规模 n 是成正比的。

知识点与总结

这道题的核心思想是贪心算法，真是个好用的工具呢！

分解问题: 我们把复杂的最小化问题分解成两个子问题：最小化剩余元素的和，以及最小化除法操作的和。这种分解让问题清晰了很多。
排序的重要性: 排序是许多贪心算法的基石！它能帮助我们快速地识别出元素的“价值”（在这里就是大小），从而做出正确的贪心选择。
贪心选择:
- 留下最小的元素，这是最直接的贪心。
- 用“较小”的数作分子，“较大”的数作分母，这也是一个很直观的贪心选择，目标是让商尽可能小。
- 一一对应配对 (a[i] 配 a[i+k]) 是一种经典的贪心策略，在很多问题中都能最小化或最大化某种配对的和。

所以，下次遇到类似的要最小化或最大化某个总和的问题时，可以先试试排序，然后思考一下能不能通过贪心，每次都做出局部最优的选择，最终达到全局最优哦！

好啦，今天的解题分享就到这里啦！希望我的讲解对你有帮助哦~ 下次再见，喵~ (ฅ'ω'ฅ)

D. Array and Operations - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路详解~ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​