E1. Close Tuples (easy version) - 题解

比赛与标签

比赛: Codeforces Round 690 (Div. 3) 标签: binary search, combinatorics, math, sortings, two pointers 难度: *1500

题目大意喵~

主人，你好呀！这道题是这样描述的：

给我们一个长度为 n 的序列 a，里面都是整数。我们的任务是，找出有多少个满足特定条件的三元组。

这个条件就是：找到三个不同的下标 i < j < z，使得这三个位置上的数 a[i], a[j], a[z] 中，最大值与最小值的差不大于 2。

简单来说，就是 max(a[i], a[j], a[z]) - min(a[i], a[j], a[z]) <= 2。

我们要做的就是数一数，有多少对这样的 (i, j, z) 组合，然后把总数告诉裁判。在这个简单版本里，k 固定为2，m 固定为3，而且答案不需要取模，直接输出就好啦！

解题思路，一爪挠破！

看到这种需要在数组里找组合，并且有大小关系的题目，小猫娘的直觉告诉我们——排序大法好！喵~

第一步：排序是关键喵！

为什么排序这么重要呢？因为题目中的条件 max(...) - min(...) <= 2 只跟数值有关，和它们在原数组中的位置无关。如果我们先把整个数组 a 从小到大排好序，事情就会变得超级简单！

排序后，对于我们选出的任意三个下标 i < j < z，由于数组已经有序，我们能立刻确定 a[i] 是最小值，a[z] 是最大值。这样一来，复杂的条件 max(a[i], a[j], a[z]) - min(a[i], a[j], a[z]) <= 2 就变成了清爽的 a[z] - a[i] <= 2。是不是一下子就清晰多啦？

第二步：双指针，优雅地滑动~

现在问题变成了：在排好序的数组里，找有多少个 i < j < z 满足 a[z] - a[i] <= 2。

如果暴力枚举所有的 i, j, z，那可是 O(N^3) 的复杂度，肯定会超时的说！所以，我们需要更聪明的办法。这时候，就轮到我们算法界的明星——双指针登场啦！

我们可以用一个指针 i 从左到右遍历数组，把 a[i] 当作我们三元组中最小的那个数。对于每个固定的 a[i]，我们需要找到所有可以和它组成合法三元组的其他两个数。

这两个数 a[j] 和 a[z] 必须满足 a[z] <= a[i] + 2。为了找到所有满足这个条件的数，我们引入第二个指针 j。

第三步：固定左端点，寻找右边界呐

我们让 i 从 0 开始遍历。对于每个 i，我们用另一个指针 j 从 i 的位置开始向右移动，直到找到第一个不满足 a[j] <= a[i] + 2 的元素。

当 j 停下来的时候，所有在区间 [i, j-1] 里的元素（也就是 a[i], a[i+1], ..., a[j-1]）都满足与 a[i] 的差不大于 2。这个区间里的任何三个数，它们的最大值和最小值的差都不会超过 2！

第四步：组合计数的魔法时间！

我们已经找到了一个“和谐”的大家庭 a[i...j-1]，它的长度是 L = j - i。现在，我们要在这个大家庭里，找出以 a[i] 为首的三元组。

既然我们已经钦定了 a[i] 是三元 z 组的一员（而且是最小的），我们只需要从剩下的 L-1 个元素（a[i+1], ..., a[j-1]）中再挑选 2 个成员就可以啦！

从 L-1 个元素中选 2 个，这是多么经典的组合问题呀！它的方案数就是组合数 C(L-1, 2)。 计算公式是：C(L-1, 2) = (L-1) * (L-2) / 2。

当然，我们得保证 L-1 至少是 2，也就是说 L 至少是 3，不然连两个元素都凑不齐，更别提三元组了。

所以，我们的算法流程就是：

1. 对数组 a 进行排序。
2. 初始化总答案 ans = 0。
3. 用一个 for 循环遍历 i 从 0 到 n-1。
4. 在循环内部，用一个 while 循环移动右指针 j，找到满足 a[j] <= a[i] + 2 的最远边界。
5. 计算窗口长度 L = j - i。
6. 如果 L >= 3，说明我们可以在这个窗口里选出以 a[i] 为首的三元组，数量为 C(L-1, 2)。将这个数量累加到 ans 上。
7. 循环结束后，ans 就是我们要求的总数啦！

这种方法保证了每个有效的三元组只会被计算一次——在它的最小元素的那个 i 被遍历到时计算。而且，j 指针只会向前移动，不会回退，所以整个双指针部分的时间复杂度是 O(N) 的说！

代码实现喵~

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

using namespace std;

int main() {
    // 加速输入输出，让程序跑得飞快喵~
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        // 排序是解题的第一步喵！这能让问题变得简单。
        sort(a.begin(), a.end());

        long long ans = 0; // 用 long long 来存答案，防止数字太大溢出哦！
        int j = 0; // 这是我们的右指针 j

        // 遍历数组，固定三元组的左端点 i
        for (int i = 0; i < n; i++) {
            // 移动右指针 j，找到满足 a[j] - a[i] <= 2 的最远位置
            // j 不会回退，保证了整体的线性复杂度
            while (j < n && a[j] <= a[i] + 2) {
                j++;
            }
            
            // 当前窗口是 [i, j-1]，长度为 L = j - i
            long long L = j - i;

            // 如果窗口内至少有3个元素，才能构成三元组
            if (L >= 3) {
                // 我们以 a[i] 为三元组的最小元素，
                // 还需要从剩下的 L-1 个元素中选出 2 个。
                // 这就是组合数 C(L-1, 2) 的计算
                ans += (L - 1) * (L - 2) / 2;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

• 时间复杂度: O(N log N) 的说。 其中 O(N log N) 是排序的开销。后面的双指针部分，i 和 j 两个指针都只从头到尾扫了一遍数组，所以这部分的复杂度是 O(N)。总的时间复杂度由排序决定，就是 O(N log N) 啦！

• 空间复杂度: O(N) 的说。 我们主要用了一个 vector<long long> a 来存储输入的 n 个数，所以空间复杂度是 O(N)。如果题目允许直接修改输入数组，那可以看作是 O(1) 的额外空间（不计输入本身）。

知识点与总结

这道题是不是很有趣呀？它完美地把好几种基础但强大的算法思想结合在了一起：

1. 排序思想: 面对无序数组中元素大小关系的问题时，排序往往是破局的神器！它能将问题转化为更有序、更结构化的形式。
2. 双指针（滑动窗口）: 这是处理有序序列上区间问题的超级高效技巧。通过维护一个“窗口”，我们可以把 O(N^2) 甚至更高的复杂度优化到 O(N)，是必须掌握的核心技能之一！
3. 组合数学: 在计数问题中，识别出“选择”的模型并运用组合数公式 C(n, k) 是非常重要的一步。
4. 数据类型: 千万要注意，当 n 很大时，组合数的结果可能非常大。n 最大是 2 * 10^5，C(n, 3) 级别的结果会轻松超出 int 的范围，所以要记得用 long long 来存答案哦！

希望这篇题解能帮到你，主人！只要掌握了这些基础的武器，再难的题目也都能被我们一爪攻破！继续加油喵~！