D. Counting Pairs - 题解

比赛与标签

比赛: Codeforces Round 995 (Div. 3) 标签: binary search, sortings, two pointers 难度: *1200

题目大意喵~

Mina-san, konnichiwa! ฅ'ω'ฅ 这里是你们最爱解题的猫娘！今天我们遇到的这道题呀，是说有一个整数序列 a，还有两个整数 x 和 y。

我们需要找到所有“有趣的”数对 (i, j) 的数量，这里的 i 必须小于 j 哦。一个数对 (i, j) 为什么有趣呢？因为如果我们把 a[i] 和 a[j] 从序列里拿走，剩下所有元素的和，会不多不少正好落在 [x, y] 这个区间里（包括 x 和 y 本身）。

简单来说，就是：

输入：一个数组 a，它的长度是 n，还有两个数字 x 和 y。
输出：满足条件的数对 (i, j) 的总数。

是不是听起来很有趣呐？让我们一起把它解决掉吧！

解题思路喵！

这道题的核心在于那个“移除两个数后，剩余和在 [x, y] 之间”的条件。直接去枚举每一对 (i, j) 然后计算剩余和，时间复杂度会是 O(N³)，这肯定会超时的说！所以我们需要更聪明的办法，喵~

第一步：条件转化！

让我们先把条件变得更友好一些。设整个序列 a 的总和是 S。如果我们移除了 a[i] 和 a[j]，那么剩下的元素之和就是 S - (a[i] + a[j])。

题目给的条件是： x <= S - (a[i] + a[j]) <= y

这是一个不等式，我们可以稍微变个形，把 a[i] + a[j] 单独拎出来：

S - (a[i] + a[j]) >= x => S - x >= a[i] + a[j]
S - (a[i] + a[j]) <= y => S - y <= a[i] + a[j]

把这两个合在一起，我们就得到了一个全新的、等价的条件： S - y <= a[i] + a[j] <= S - x

看吧！问题一下子就清晰了！我们不再关心“剩余的和”，而是要找有多少对 (i, j) (其中 i < j)，它们的和 a[i] + a[j] 落在 [S - y, S - x] 这个新的区间里。我们把这个新区间叫做 [L, R]，其中 L = S - y，R = S - x。

第二步：计数魔法！

现在问题变成了：在一个数组里，找和在 [L, R] 范围内的数对数量。直接数这个范围内的还是有点麻烦，但我们可以用一个经典的计数技巧，就像“前缀和”思想一样，喵~

求 [L, R] 区间内的数量 = (小于等于 R 的数量) - (小于 L 的数量)

也就是说，我们可以设计一个函数 countPairs(T)，它能计算出满足 a[i] + a[j] <= T 的数对数量。那么最终的答案就是 countPairs(R) - countPairs(L - 1) 啦！

第三步：双指针大法！

那么，countPairs(T) 这个函数要怎么实现呢？这就要请出我们的老朋友——双指针了！

排序：首先，我们必须把数组 a 从小到大排个序。排序是使用双指针的前提，它能保证单调性，让指针可以愉快地单向移动，喵~
设置指针：我们用两个指针，i 从数组的开头 0 开始，j 从数组的末尾 n-1 开始。
移动与计数：
- 我们固定住指针 i，然后去寻找有多少个 j (必须 j > i) 能够满足 a[i] + a[j] <= T。
- 因为数组是排好序的，如果当前的 a[i] + a[j] > T，说明 a[j] 太大了，我们就需要把 j 指针向左移动 (j--) 来找一个更小的数。
- 我们一直移动 j，直到 a[i] + a[j] <= T 或者 j 不再大于 i 为止。
- 当我们为当前的 i 找到了一个合适的 j 时，因为数组的有序性，对于所有在 i 和 j 之间的下标 k (i < k <= j)，都必然满足 a[i] + a[k] <= a[i] + a[j] <= T。
- 所以，对于固定的 i，所有从 i+1 到 j 的下标都可以和 i 组成满足条件的数对。这样的数对有 j - i 个！我们把这个数量加到总数里。
- 然后我们把 i 指针向右移动 i++，继续寻找下一轮。因为 a[i] 变大了，j 指针不需要重置回 n-1，它可以从当前位置继续向左移动，因为我们需要的配对值只会更小。这就是双指针效率高的原因，两个指针总共只会扫一遍数组！

通过这个方法，我们就能在 O(N) 的时间内完成 countPairs(T) 的计算。加上排序的时间，总的解法就非常高效啦！

代码实现喵~

cpp

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

using namespace std;

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

    int t;
    cin >> t;
    while (t--) {
        long long n, x, y;
        cin >> n >> x >> y;
        vector<long long> a(n);
        long long total = 0;
        // 读入数组并计算总和 S
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            total += a[i];
        }

        // 根据我们的推导，计算出数对和的目标区间 [L, R]
        // L = total - y, R = total - x
        long long L0 = total - y;
        long long R0 = total - x;

        // 双指针算法的前提是数组有序！
        sort(a.begin(), a.end());

        // 定义一个 lambda 函数来计算 a[i] + a[j] <= T 的数对数量
        auto countPairs = [&](long long T) -> long long {
            long long cnt = 0;
            int j = n - 1; // j 指针从最右边开始
            for (int i = 0; i < n; i++) { // i 指针从最左边开始
                // 移动 j 指针，找到第一个满足 a[i] + a[j] <= T 的位置
                // 如果 a[i] + a[j] 太大了，j 就需要向左移动
                while (j > i && a[i] + a[j] > T) {
                    j--;
                }
                
                // 如果 j 移动到了 i 的左边或与 i 相遇，说明对于当前的 i 和之后所有的 i'
                // 都找不到满足条件的 j 了，因为 a[i'] >= a[i]
                if (j <= i) {
                    break;
                }

                // 对于当前的 i，所有从 i+1 到 j 的下标 k 都能满足 a[i] + a[k] <= T
                // 这样的下标有 j - i 个
                cnt += (j - i);
            }
            return cnt;
        };

        // 使用我们的计数魔法！
        // (和 <= R0 的对数) - (和 <= L0-1 的对数) = (和在 [L0, R0] 区间的对数)
        long long ans = countPairs(R0) - countPairs(L0 - 1);
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N log N) 的说。
- 首先，计算总和 total 需要 O(N) 的时间。
- 接着，std::sort 对数组排序，这是整个算法中耗时最长的部分，时间复杂度为 O(N log N)。
- countPairs 函数使用了双指针技术。指针 i 从头到尾走一遍，指针 j 从尾到头走一遍，每个指针最多移动 N 次，所以函数本身的复杂度是 O(N)。
- 我们调用了两次 countPairs 函数，总时间是 O(N) + O(N log N) + O(N) + O(N)，由排序主导，所以总体是 O(N log N)。对于这道题的数据范围来说，是完全没问题的！
空间复杂度: O(N) 的说。
- 我们需要一个 vector<long long> a 来存储输入的 n 个整数，所以空间复杂度是 O(N)。std::sort 在一些实现中可能会使用 O(log N) 的递归栈空间，但主要还是由存储数组的 O(N) 决定。

知识点与总结喵

这道题真是一次愉快的冒险呢！我们来总结一下这次冒险中学到的宝藏吧：

问题转化：这是解题的第一步，也是最关键的一步！学会把复杂、间接的条件（剩余和在区间内）转化为简单、直接的条件（两数和在另一区间内），是成为算法大师的必经之路呐。
计数技巧（容斥原理）：count(R) - count(L-1) 的思想非常强大！它把一个“区间计数”问题分解成了两个“前缀计数”问题，大大简化了逻辑。这个技巧在很多计数类题目中都会用到哦。
双指针算法：在 有序数组 中查找满足条件的数对时，双指针是一个非常高效的工具。它利用单调性，避免了不必要的重复搜索，将 O(N²) 的暴力枚举优化到了 O(N)。
排序的重要性：很多高级算法（如双指针、二分查找）都依赖于数据的有序性。所以，当你看到一道题感觉毫无头绪时，不妨先试试排序，说不定就能打开新世界的大门，喵~

希望这篇题解能帮助到你！继续努力，享受每一道题带来的挑战与乐趣吧！加油，你一定可以的！(ฅ^•ﻌ•^ฅ)

D. Counting Pairs - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路喵！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结喵 ​