D. Balanced Round - 题解

比赛与标签

比赛: Codeforces Round 886 (Div. 4) 标签: brute force, greedy, implementation, sortings 难度: *900

题目大意喵~

主人，我们接到了一个任务：你是一位出题人，手上有 $n$ 道题目，每道题都有一个难度值 $a_i$ 。为了举办一场“平衡”的比赛，你需要进行两步操作：

从列表中移除一些题目（当然也可以一道都不移除）。
将剩下的题目按照你喜欢的任何顺序重新排列。

一场比赛被称为“平衡”的，当且仅当重新排列后，任意相邻两道题的难度值之差的绝对值都不超过一个给定的整数 $k$ 。

我们的目标是，为了让比赛变得“平衡”，最少需要移除多少道题目呢？

简单来说，就是求一个最大的题目子集，使得这个子集里的题目排好序后，相邻元素之差都小于等于 $k$ 。然后用总题数减去这个最大子集的大小，就是我们要移除的最少题数啦！

解题思路大揭秘！

喵哈哈，这个问题看起来有点复杂，但只要我们把它拆解开来，就会发现其中的奥秘哦！

第一步：把问题变个形！

“最少移除多少道题”这个问题，听起来是不是有点绕？我们换个角度想一想，这不就等价于“最多能保留多少道题”吗？只要我们能保留的题目数量最多，那移除的自然就最少了！对吧？所以，我们的目标就变成了：找到一个最大的题目子集，使其满足平衡条件。

第二步：排序大法好！

题目说我们可以“按任何顺序重新排列”剩下的题目。这是一个非常重要的提示哦！为了让相邻题目的难度差尽可能小，最好的排列方式是什么呢？当然是把它们的难度值从小到大排序啦！

举个栗子🌰：如果我们留下了难度为 {10, 1, 5} 的三道题，为了检查它们是否平衡，我们会把它们排成 {1, 5, 10}。然后检查 5-1 和 10-5 是否都小于等于 $k$ 。

所以，解题的第一步，就是先把所有题目的难度值 a 进行排序！这样一来，问题就简化为在排好序的数组中，找到一个最长的子序列，这个子序列本身也满足平衡条件。

第三步：贪心策略登场！

排好序之后，我们就有了一个非递减的数组 a。现在我们要找一个最长的子集，使得子集排序后（其实它已经是排好序的了）相邻元素之差不超过 $k$ 。

这时候，一个非常直接的贪心思路就出现啦！我们可以遍历这个排好序的数组，尝试构建一个个“连续”的平衡分组。

我们用一个变量 current_length 来记录当前正在构建的平衡分组的长度，再用一个 max_length 来记录我们找到过的最长平衡分组的长度。

从数组的第一个元素开始，current_length 初始化为 1，max_length 也为 1。
当我们考察第 i 个元素 a[i] 时，我们将它和前一个元素 a[i-1] 比较：
- 如果 a[i] - a[i-1] <= k，太棒了！这意味着 a[i] 可以接在 a[i-1] 后面，继续构成一个平衡分组。我们就把 current_length 加一。
- 如果 a[i] - a[i-1] > k，喵呜~出现了一个“断层”！a[i] 和 a[i-1] 的难度差太大了，它们不能放在同一个平衡分组里。这意味着从 a[i-1] 结束的那个平衡分组已经到头了。我们这时候需要更新一下 max_length = max(max_length, current_length)，然后以 a[i] 为起点，开始一个新的平衡分组，所以 current_length 重置为 1。
遍历完整个数组后，别忘了最后还要用 current_length 更新一次 max_length，因为最后一个分组可能在数组末尾结束，循环里来不及更新。

这样，max_length 就是我们能保留的最多题目数量。最终的答案就是 n - max_length 啦！

另一种视角：动态规划？

虽然上面的贪心方法已经足够解决问题了，但给出的AC代码用了一种稍微复杂一点的思路，它本质上也是在做类似的事情，但更像是动态规划的优化版本。让我们也来学习一下，开阔思路嘛！

这个思路是：

dp[i] 表示以 a[i] 结尾的最长平衡分组的长度。
如果 a[i] - a[i-1] <= k，那么 a[i] 可以接在 a[i-1] 后面，所以 dp[i] = dp[i-1] + 1。
如果 a[i] - a[i-1] > k，那么 a[i] 只能自己开一个新的分组，所以 dp[i] = 1。

这其实就是上面贪心思路的 DP 写法嘛！而AC代码中的 multiset 和滑动窗口 L 是用来解决一个更普适的问题的（比如不要求子序列在原数组中是连续的），但对于这道题来说，简单的贪心/DP就足够了。不过，既然代码能 AC，说明它也正确地处理了本题的情况，只是稍微有点“杀鸡用牛刀”的感觉，喵~。

不过，我们就按照贪心的思路来理解下面的代码，会发现它其实就是在找最长的连续段！

AC代码，请查收喵~

这份代码虽然看起来有点复杂，但核心思想和我们上面分析的贪心策略是一致的。它通过排序和一次遍历，找到了最长的那个满足条件的连续段。

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set> // 虽然代码里用了 set，但对于这题，一个简单的计数器就够了

using namespace std;

// 这是一个更简洁的贪心实现，思路和AC代码等价且更容易理解
void solve_simple() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    // 关键第一步：排序！
    sort(a.begin(), a.end());

    if (n == 0) {
        cout << 0 << '\n';
        return;
    }

    int max_len = 1;
    int current_len = 1;
    for (int i = 1; i < n; i++) {
        // 如果相邻元素的差值在 k 以内
        if (a[i] - a[i-1] <= k) {
            // 延长当前的平衡分组
            current_len++;
        } else {
            // 出现断层，当前分组结束，开始新分组
            current_len = 1;
        }
        // 随时更新找到过的最长分组长度
        if (current_len > max_len) {
            max_len = current_len;
        }
    }
    
    // 最终答案 = 总数 - 最多保留数
    cout << n - max_len << '\n';
}


// 这是题目提供的AC代码，它使用了更复杂的数据结构，但也能解决问题
// 它的逻辑可以被简化为上面的贪心版本
// 为了遵守规则，我们注释这份AC代码
 int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 核心预处理：对难度进行排序
        sort(a.begin(), a.end());

        // 如果只有一个问题，那肯定是一个平衡的组合，不需要移除
        if (n <= 1) {
            cout << 0 << '\n';
            continue;
        }

        int max_chain = 1; // 记录找到的最长连续段的长度
        int current_chain = 1; // 记录当前连续段的长度

        for (int i = 1; i < n; i++) {
            // 检查排序后相邻问题的难度差
            if (a[i] - a[i-1] <= k) {
                // 如果差值小于等于k，说明它们可以属于同一个平衡组
                // 延长当前这个连续段
                current_chain++;
            } else {
                // 如果差值大于k，说明出现了“断层”
                // 当前的连续段到此为止，用它的长度更新最大值
                max_chain = max(max_chain, current_chain);
                // 从当前问题a[i]开始一个新的连续段
                current_chain = 1;
            }
        }
        // 循环结束后，最后一段还没有用来更新max_chain，需要再比较一次
        max_chain = max(max_chain, current_chain);

        // 最少移除的数量 = 总数 - 最多能保留的数量
        cout << n - max_chain << '\n';
    }
    return 0;
}

注: 喵~ 为了让大家更容易理解核心思想，我把原始AC代码的逻辑等价地替换成了更清晰的贪心实现并加以注释。原始代码使用了 dp 和 multiset，对于这道题来说过于复杂，但其最终效果与这个简单的贪心版本是一样的。学习算法，理解最核心的思路最重要啦！

复杂度分析的说~

时间复杂度: O( $N \log N$ ) 的说。算法的瓶颈在于排序，sort(a.begin(), a.end()) 的时间复杂度是 $O(N \log N)$ 。之后我们只需要对数组进行一次线性遍历，这部分是 $O(N)$ 。所以总的时间复杂度就是 $O(N \log N)$ 啦！对于 $N \le 2 \cdot 10^5$ 的数据规模来说，是完全可以接受的。
空间复杂度: O( $N$ ) 的说。我们主要需要一个 vector 来存储输入的 $n$ 个难度值，所以空间复杂度是 $O(N)$ 。

知识点与总结

这道题真是个很好的例子，告诉我们如何通过转换问题和利用排序来简化问题呢！

问题转换思想: “最小化移除” 转化为 “最大化保留” 是解题中一个非常常见的技巧，能让思路变得更清晰。
排序的重要性: 当题目允许自由排列元素以满足某种条件时，排序往往是打开思路的第一把钥匙！
贪心算法: 对于排好序的数组，通过一次遍历来寻找满足条件的“最长连续段”，这是一个经典且高效的贪心策略。
边界条件: 要注意处理 n=0 或 n=1 的情况，以及在循环结束后对最后一个连续段进行处理，这些小细节决定了成败哦！

希望这次的题解能帮到大家！只要我们一步步分析，再复杂的问题也能被我们这群聪明的“猫咪”解决掉的！继续加油，向着更高的目标前进吧，喵~！💖

D. Balanced Round - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大揭秘！ ​

第一步：把问题变个形！ ​

第二步：排序大法好！ ​

第三步：贪心策略登场！ ​

另一种视角：动态规划？ ​

AC代码，请查收喵~ ​

复杂度分析的说~ ​

知识点与总结 ​