G1. Dances (Easy version) - 题解

比赛与标签

比赛: Codeforces Round 905 (Div. 3) 标签: binary search, greedy, two pointers, *1400 难度: *1400

喵喵，题目说什么呀？

这道题是说，我们有两组舞者，分别在队伍 a 和队伍 b 里，每队都有 n 个人。我们可以随~意~地重新排列两队的顺序。然后呢，我们可以进行一种“操作”：从 a 队里请走一个人，同时从 b 队里也请走一个人。

我们的目标是，通过最少的操作次数，让剩下的两队（假设各有 k 个人）能够一一配对，并且满足 a 队的第 i 个人要比 b 队的第 i 个人矮，也就是 a_i < b_i 必须对所有留下的 i 都成立。

简单来说，就是问我们最少要淘汰掉多少对舞者，才能让剩下的人完美配对。

在简单版本里，m=1，这意味着 a 队的人员是固定的：第一个人的身高是 1，剩下 n-1 个人的身高由输入决定。

把问题换个说法就更清晰啦：我们要尽可能多地保留舞者，也就是找出最多能凑成多少对 (a_i, b_i) 满足 a_i < b_i。如果我们能凑出 k_max 对，那么需要淘汰的人数就是 n - k_max 对，也就是需要 n - k_max 次操作，对吧喵？

本喵的贪心小妙招！

一看到“可以任意重新排列”，本喵的猫耳朵就竖起来了！这通常是一个强烈的信号：排序！喵~

没错，我们可以先把 a 队和 b 队的所有人都按身高从小到大排个序。这样一来，处理起来就方便多啦。

排好序之后，我们该如何配对才能让成功配对的数量最多呢？这里就要用到贪心的思想啦！

想象一下，我们是 a 队的经纪人，要为我们的队员找舞伴。

首先，看看我们队里最矮的队员 a[0]。为了给他找个舞伴，我们需要从 b 队里找一个比他高的。
那应该找哪个呢？是找一个刚刚好比他高的，还是找一个最高的呢？
当然是找一个刚刚好比他高的啦！如果我们把 b 队里最高的队员分给了我们最矮的 a[0]，那我们队里那些高个子队员可能就找不到舞伴了，这太浪费了对不对？把珍贵的高个子 b 队员留给高个子 a 队员，这才是最划算的策略！

这个贪心策略可以推广到 a 队的所有人：对于 a 队的每一个队员 a[i]，我们都应该为他寻找 b 队中还未被匹配的、且身高大于 a[i] 的队员里最矮的那一个。

这个策略听起来很棒，要怎么实现呢？用双指针就再合适不过了！

将数组 a 和 b 都进行升序排序。
我们用一个指针 i 指向 a 数组的开头，一个指针 j 指向 b 数组的开头。
我们开始遍历 a 数组（用指针 i）。对于当前的 a[i]，我们就在 b 数组里为他寻找舞伴（移动指针 j）。
我们不断地向后移动 j，直到找到第一个 b[j] 满足 b[j] > a[i]。
如果找到了（也就是说 j 没有超出 b 数组的范围），太棒了！我们成功为 a[i] 找到了一个舞伴 b[j]。这时，成功配对数 count 加一，并且这个 b[j] 已经被“预定”了，所以下一次为 a[i+1] 寻找舞伴时，要从 b[j+1] 开始找。所以我们把 j 也向后移动一位。
如果在寻找的过程中，b[j] 一直小于等于 a[i]，说明这个 b[j] 太矮了，连 a[i] 都配不上。因为 a 数组是排好序的，所以这个 b[j] 肯定也配不上后面更高的 a[i+1], a[i+2], ...。所以这个 b[j] 就直接淘汰掉，我们继续看下一个 b[j+1] 能不能配上 a[i]。
我们让指针 i 遍历完整个 a 数组，最终得到的 count 就是我们能凑成的最大配对数 k_max。
那么，最少的操作次数就是 n - count 啦！

代码魔法时间喵~

下面就是实现这个思路的魔法代码，本喵已经加上了详细的注释，让你一目了然的说！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    // 加速输入输出，让程序跑得像猫一样快~
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m; // m 在这个版本里总是 1

        vector<long long> a;
        a.push_back(1); // 根据题目，a[0]固定为1
        for (int i = 0; i < n - 1; i++) {
            long long x;
            cin >> x;
            a.push_back(x);
        }

        vector<long long> b(n);
        for (int i = 0; i < n; i++) {
            cin >> b[i];
        }

        // 排序是贪心策略的基础喵！
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        int j = 0; // 这是指向数组 b 的指针
        int count = 0; // 这是成功配对的数量

        // 遍历数组 a 中的每一个元素
        for (int i = 0; i < n; i++) {
            // 为 a[i] 寻找一个比它大的 b[j]
            // 如果 b[j] 不够大，它也肯定配不上后面更大的 a 元素，所以 j 可以放心地往后走
            while (j < n && b[j] <= a[i]) {
                j++;
            }

            // 如果 j 没有越界，说明我们为 a[i] 找到了一个合适的舞伴 b[j]
            if (j < n) {
                count++; // 配对成功！计数器+1
                j++;     // 这个 b[j] 已经被匹配了，下一个 a 元素要从下一个 b 元素开始找
            }
        }

        // 总人数 n 减去最大配对数 count，就是最少需要进行的操作数
        cout << n - count << '\n';
    }
    return 0;
}

时空消耗分析的说

时间复杂度: O(N log N) 的说。为啥呢？因为程序中最耗时的部分是排序 a 和 b 两个数组，每个排序都需要 O(N log N) 的时间。后面的双指针遍历部分，两个指针 i 和 j 都只会从头到尾走一遍，所以是 O(N) 的时间。总的时间复杂度就是 O(N log N + N) = O(N log N) 啦！
空间复杂度: O(N) 的说。我们主要需要空间来存储 a 和 b 两个数组，每个数组的大小都是 N，所以空间复杂度就是 O(N) 呐。

猫娘的小课堂~

这道题是不是很有趣呀？通过它我们可以学到一些重要的思想哦！

贪心大法好 (Greedy): 贪心算法的核心就是“只看眼前，做出最好选择”。在这道题里，为每个 a 队员选择“刚刚好”的 b 队员就是局部最优解，而这一系列局部最优解最终导向了全局最优解（最多的配对数）。
双指针技巧 (Two Pointers): 当你处理两个排好序的数组时，双指针是一个超级有用的工具！它能让你用线性的时间复杂度完成匹配、查找等任务，非常高效。
问题转化: 把“最小化操作数”转化为“最大化保留数”是解题的关键一步！很多时候，换个角度看问题，思路就会豁然开朗，喵~

希望本喵的讲解对你有帮助！如果还有不懂的地方，随时可以再来问我哦！一起加油，成为更厉害的算法大师吧！喵~ (ฅ'ω'ฅ)

G1. Dances (Easy version) - 题解 ​

比赛与标签 ​

喵喵，题目说什么呀？ ​

本喵的贪心小妙招！ ​

代码魔法时间喵~ ​

时空消耗分析的说 ​

猫娘的小课堂~ ​