G. 2^Sort - 题解

比赛与标签

比赛: Codeforces Round 799 (Div. 4) 标签: data structures, dp, sortings, two pointers 难度: *1400

喵喵，题目在说什么呀？

你好呀，我是乐于助人的猫娘！这道题其实超级有趣的，让本喵带你一起看看吧~

题目会给我们一个长度为 n 的数组 a 和一个整数 k。我们的任务是，找出有多少个起始位置 i（从 1 到 n-k），使得从 a_i 开始，长度为 k+1 的子数组 [a_i, a_{i+1}, ..., a_{i+k}] 满足一个特殊的“2的幂次排序”性质。

这个性质是这样的： 1 * a_i < 2 * a_{i+1} < 4 * a_{i+2} < ... < 2^k * a_{i+k}

简单来说，就是把子数组的第 j+1 个元素（a_{i+j}）乘以 2^j 之后，整个序列是严格递增的。我们要做的就是数一数，有多少个这样的子数组，喵~

解题思路大揭秘喵！

看到这一长串带幂次的 inequalities（不等式），是不是有点头晕呀？别怕别怕，看我一招猫猫拳，化繁为简喵！

2^0⋅a_i < 2^1⋅a_{i+1} < 2^2⋅a_{i+2} < ⋯ < 2^k⋅a_{i+k}

这一长串不等式，其实可以拆解成 k 个独立的小不等式，它们必须同时成立：

2^0 * a_i < 2^1 * a_{i+1}
2^1 * a_{i+1} < 2^2 * a_{i+2}
... k. 2^{k-1} * a_{i+k-1} < 2^k * a_{i+k}

现在我们来研究其中任意一个不等式，比如第 j 个（0 <= j < k）： 2^j * a_{i+j} < 2^{j+1} * a_{i+j+1}

两边都是正数，我们可以放心地同时除以 2^j，不等号方向不变： a_{i+j} < (2^{j+1} / 2^j) * a_{i+j+1}a_{i+j} < 2 * a_{i+j+1}

哇！你看！原来那个复杂的、带有 j 的幂次条件，变成了一个超级简单的、只和相邻两个元素有关的条件：前一个元素必须小于后一个元素的两倍。这个规律对所有 k 个小不等式都成立！

所以，原问题就等价于： 找到有多少个起始位置 i，使得从 p = i 到 p = i+k-1，都满足 a_p < 2 * a_{p+1}。

这下问题就清晰多啦！我们可以先预处理一下，创建一个辅助数组 valid。valid[p] 就用来记录 a_p < 2 * a_{p+1} 这个条件是否成立。如果成立，valid[p] = 1；不成立，valid[p] = 0。这个辅助数组的长度是 n-1。

现在，一个从 i 开始的长度为 k+1 的子数组是合法的，当且仅当 valid[i], valid[i+1], ..., valid[i+k-1] 这 k 个值 全部都是 1。换句话说，这 k 个值的和必须等于 k。

这不就是经典的 滑动窗口 问题嘛！滑动窗口，启动喵！

我们维护一个大小为 k 的窗口，在 valid 数组上滑动。
首先，计算第一个窗口（从 valid[0] 到 valid[k-1]）里所有元素的和。如果和为 k，说明找到了一个满足条件的子数组，计数器加一。
然后，将窗口向右滑动一格。我们不需要重新计算整个窗口的和，只需要用上一个窗口的和，减去离开窗口的那个元素 valid[i-1]，再加上新进入窗口的元素 valid[i+k-1]。这样更新超快的说！
每次滑动后，都检查一下新的窗口和是不是 k。如果是，计数器再加一。
重复这个过程，直到窗口滑到 valid 数组的末尾。

这样一来，我们只需要遍历数组一次进行预处理，再遍历一次来滑动窗口，总的时间复杂度就是线性的，非常高效，完全不会超时，喵~

代码时间到，开饭啦喵！

cpp

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

int main() {
    // 加速输入输出，让程序跑得像猫一样快，喵~
    ios_base::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];
        }

        // 这是我们的辅助数组，nya!
        // valid[i] = 1 表示 a[i] < 2 * a[i+1] 成立
        vector<int> valid(n - 1);
        for (int i = 0; i < n - 1; i++) {
            // 这里就是我们推导出的核心简化条件！
            // 用 2LL 来保证是 long long 类型，防止和 a[i+1] 相乘时溢出
            if (a[i] < 2LL * a[i + 1]) {
                valid[i] = 1;
            } else {
                valid[i] = 0;
            }
        }

        int total = 0; // 最终的答案计数器
        int window_sum = 0; // 滑动窗口内1的个数

        // 初始化第一个窗口（大小为 k）的和
        // 这个窗口对应检查 a[0]...a[k] 这个子数组
        for (int i = 0; i < k; i++) {
            window_sum += valid[i];
        }
        
        // 如果第一个窗口的和就是 k，说明所有条件都满足
        if (window_sum == k) {
            total++;
        }

        // 开始滑动窗口，从第二个窗口开始
        // 窗口的起始位置 i 从 1 到 n-1-k
        for (int i = 1; i <= n - 1 - k; i++) {
            // 高效更新窗口的和：减去离开的元素，加上新进入的元素
            window_sum = window_sum - valid[i - 1] + valid[i + k - 1];
            
            // 检查新窗口的和是否为 k
            if (window_sum == k) {
                total++;
            }
        }

        cout << total << '\n';
    }
    return 0;
}

效率分析喵~

时间复杂度: O(n) 的说。我们首先用 O(n) 的时间遍历一次原数组来构建 valid 数组。然后，滑动窗口的过程也只遍历了 valid 数组一次，这也是 O(n) 的。总的来说就是 O(n)，对于 n 最大到 2*10^5 的数据完全没问题！
空间复杂度: O(n) 的说。我们创建了一个 valid 数组来辅助计算，它的大小是 n-1，所以占用了 O(n) 的额外空间。

猫娘的小课堂时间~

这道题真的很有启发性呢，让我们来总结一下学到了什么吧！

问题转化 (Problem Transformation): 这是解题最最关键的一步！把一个看起来很复杂的、带有幂次的不等式链，通过简单的代数变换，化简为对所有相邻元素都成立的简单条件 a_p < 2 * a_{p+1}。在做题时，如果遇到复杂的数学公式，一定要尝试去化简它，说不定就豁然开朗了呢！
滑动窗口 (Sliding Window): 当题目要求我们处理一个固定大小的连续子数组（窗口）时，滑动窗口是一个非常强大的工具。它的精髓在于 O(1) 的高效更新，避免了每次都对窗口内所有元素进行重复计算。
预处理 (Preprocessing): 我们先花时间构建 valid 数组，这个过程就是预处理。它把原问题中的判断逻辑提取出来，使得后续的滑动窗口逻辑变得非常纯粹和简单：就是数一个窗口里有多少个1。好的预处理能让核心算法更清晰、更高效。
编程小细节: 在 C++ 中，当一个 int 类型的数和一个 long long 类型的数进行运算时，要注意潜在的整数溢出。比如 2 * a[i+1]，如果 a[i+1] 很大，2 又是 int，可能会在相乘时出问题。写成 2LL * a[i+1] 就能确保乘法在 long long 精度下进行，这样就安全多啦！

希望这篇题解能帮到你，如果还有其他问题，随时可以再来找我玩哦！一起加油，喵~

G. 2^Sort - 题解 ​

比赛与标签 ​

喵喵，题目在说什么呀？ ​

解题思路大揭秘喵！ ​

代码时间到，开饭啦喵！ ​

效率分析喵~ ​

猫娘的小课堂时间~ ​