Odd-Even Subsequence - 题解

比赛与标签

比赛: Codeforces Round 651 (Div. 2) 标签: binary search, dp, dsu, greedy, implementation 难度: *2000

Nya~ 题目讲了什么呀？

主人，你好喵~ 今天我们来攻略一道很有趣的题目哦！(ฅ'ω'ฅ)

这道题是这样哒：我们有一个数组 a 和一个整数 k。我们的任务是从 a 里面，按照原来的顺序，挑出 k 个数，组成一个新的序列，我们叫它子序列 s。

这个子序列 s 有一个很特别的“代价 (cost)”计算方式。它的代价等于下面两个值中，比较小的那一个：

子序列 s 中，所有奇数位置（第1、3、5...个）上元素的最大值。
子序列 s 中，所有偶数位置（第2、4、6...个）上元素的最大值。

举个例子喵~ 比如子序列是 {7, 5, 6}：

奇数位置是 s_1=7, s_3=6，最大值是 max(7, 6) = 7。
偶数位置是 s_2=5，最大值是 max(5) = 5。
所以这个子序列的代价就是 min(7, 5) = 5。

我们的最终目标，就是找到一个长度为 k 的子序列，让它的代价最小。输出这个最小的代价就可以啦！

猫猫的思考时间！

一看到“最小化最大值”或者“最大化最小值”这类问题，猫猫的雷达就响了！这通常是一个强烈的信号，告诉我们可以使用一个非常强大的魔法——二分答案，喵！

为什么呢？我们可以想一下，假如我们能找到一个代价为 x 的子序列，那么对于任何大于 x 的代价 y，我们肯定也能做到，对吧？因为 x 能满足的条件，y 肯定也能满足，限制反而更宽松了呢。反过来，如果代价 x 都无法实现，那比 x 更小的代价就更不可能实现了。

这种单调性就是二分答案的魔法咒语！它让我们能把一个“求解最优值”的问题，转化成一个“判断可行性”的问题。

所以，我们的思路是：

二分枚举最终的答案（也就是最小代价），我们猜一个代价 x。
写一个 check(x) 函数，来判断是否存在一个长度为 k 的子序列，其代价不超过 x。
根据 check(x) 的结果来调整二分范围，最终找到最小的那个可行的 x。

那么，核心问题就变成了如何实现 check(x) 函数啦！

根据代价的定义 min(max_odd, max_even) <= x，这意味着只要下面两个条件至少满足一个，x 就是一个可行的代价：

奇数位受限：存在一个长度为 k 的子序列，它所有奇数位上的元素都 <= x。
偶数位受限：存在一个长度为 k 的子序列，它所有偶数位上的元素都 <= x。

我们只要分别检查这两种情况就好啦。对于每一种情况，要如何判断是否存在这样的子序列呢？当然是用贪心策略啦！为了让子序列尽可能长，我们应该从头到尾扫描原数组 a，只要遇到符合条件的数字，就毫不犹豫地把它加到我们的子序列里，喵~

让我们来模拟一下奇数位受限的情况：

我们需要构建一个长度为 k 的子序列 s。
当我们要找第 1, 3, 5... 个元素时（也就是奇数位），我们必须从原数组 a 中找一个 <= x 的数。
当我们要找第 2, 4, 6... 个元素时（也就是偶数位），没有限制，任何数都可以！

为了让子序列尽可能长，我们的贪心策略是：

遍历原数组 a。
维护一个当前子序列的长度 len。
如果 len 是偶数（意味着下一个要放的是第 1, 3, 5... 个，即奇数位），我们就必须找一个 a[i] <= x 的数，找到就把它放进来，len++。
如果 len 是奇数（意味着下一个要放的是第 2, 4, 6... 个，即偶数位），没有限制，我们直接把当前的 a[i] 放进来，len++。

我们对奇数位受限和偶数位受限这两种情况都用这个贪心策略跑一遍。只要有一种情况能构造出长度 >= k 的子序列，check(x) 就返回 true，说明 x 这个代价是可行的！

让代码开口说话喵！

cpp

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

/**
 * @brief 检查是否存在一个长度为 k 的子序列，其代价最多为 x，喵~
 *
 * 代价最多为 x 的意思是：
 * 1. 子序列奇数位置上的元素最大值 <= x。
 * 或者
 * 2. 子序列偶数位置上的元素最大值 <= x。
 *
 * 这个函数会用贪心的方法检查这两种情况。为了让子序列尽可能长，
 * 我们会遍历原数组 'a'，贪心地选择满足当前位置限制的最早出现的元素。
 *
 * @param x 我们二分猜测的代价上限。
 * @param n 原数组的大小。
 * @param k 目标子序列的长度。
 * @param a 原数组。
 * @return 如果能找到一个合法的子序列，就返回 true，否则返回 false 呐。
 */
bool check(int x, int n, int k, const std::vector<int>& a) {
    // 检查两种情况：奇数位受限，或偶数位受限
    for (int constrained_parity = 0; constrained_parity <= 1; ++constrained_parity) {
        // constrained_parity = 0: 奇数位(1,3,...)受限，对应子序列长度 len = 0, 2, 4...
        // constrained_parity = 1: 偶数位(2,4,...)受限，对应子序列长度 len = 1, 3, 5...
        
        int len = 0; // 当前构建的子序列的长度
        for (int i = 0; i < n; ++i) {
            // len % 2 代表下一个要放的元素是第 len+1 个，它的奇偶性
            // 比如 len=0，下一个是第1个，奇数位，len%2=0
            if (len % 2 == constrained_parity) { // 这个位置是受限制的
                if (a[i] <= x) {
                    len++; // 找到一个符合条件的数，加进来！
                }
            } else { // 这个位置是不受限制的
                len++; // 随便一个数都可以，直接加进来！
            }
        }
        
        // 如果贪心构造出的子序列长度达标了
        if (len >= k) {
            return true; // 说明 x 这个代价是可行的，太棒了喵！
        }
    }
    
    // 两种情况都试过了，还是不行，说明 x 太小了
    return false;
}

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

    int n, k;
    std::cin >> n >> k;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    // 二分答案的范围，从 1 到数组中可能的最大值 10^9
    int low = 1, high = 1e9;
    int ans = 1e9; // 用一个很大的数初始化答案

    while (low <= high) {
        int mid = low + (high - low) / 2; // 防止溢出的写法
        if (check(mid, n, k, a)) {
            // 如果 mid 这个代价可行，说明答案可能就是 mid，或者更小
            ans = mid;
            high = mid - 1; // 尝试更小的代价
        } else {
            // 如果 mid 不可行，说明代价太小了，需要提高
            low = mid + 1;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

复杂度分析

时间复杂度: O(N log A) 的说。这里的 N 是数组 a 的长度，A 是数组中元素的最大值（也就是 10^9）。二分答案的过程需要 log(A) 次迭代，每次迭代都会调用 check 函数。check 函数内部会遍历原数组两次，所以它的复杂度是 O(N)。所以总的时间复杂度就是 O(N * logA) 啦！
空间复杂度: O(N) 的说。我们主要的空间开销是存储输入的数组 a，所以空间复杂度就是 O(N) 喵~

小猫咪的秘籍宝典！

这道题真是一道非常经典的教学题呢，主人！它教会了我们：

二分答案 (Binary Search on Answer): 这是解决“最大值最小化”或“最小值最大化”问题的标准利器。核心思想是把求解问题转化为判定问题。
贪心策略 (Greedy Approach): 在判定一个解是否可行时（check函数），贪心往往是最高效的策略。这里的贪心体现在：为了让子序列尽可能长，我们总是选择原数组中满足当前条件的最靠前的元素。
问题转化 (Problem Transformation): 我们成功地把一个复杂的“寻找最优子序列”问题，转化成了两个更简单的“贪心构造最长子序列”问题。这种化繁为简的能力在算法竞赛中超级重要哦！
注意细节: 要小心子序列的下标是从 1 开始的，但在代码里我们通常用 0-indexed 的长度 len 来判断。len 为 0, 2, 4... 对应的是子序列的第 1, 3, 5... 个位置（奇数位），一定要对应好喵~

是不是感觉豁然开朗了呢？只要掌握了二分答案这个强大的工具，很多难题都会变得可爱起来哦！继续加油，主人！喵~ ( ´ ▽ ` )ﾉ

Odd-Even Subsequence - 题解 ​

比赛与标签 ​

Nya~ 题目讲了什么呀？ ​

猫猫的思考时间！ ​

让代码开口说话喵！ ​

复杂度分析 ​

小猫咪的秘籍宝典！ ​