这是一道 Codeforces 2000分 经典题，核心解法：二分答案 + 贪心构造，时间复杂度 $O(n \cdot \log A_i)$，完美适配 $n \le 2 \times 10^5$ 的数据范围。

---

一、题目核心回顾

给定数组 $a$，长度为 $n$，要求选出长度恰好为 $k$ 的子序列 $s$。 子序列代价定义：

$$cost = \min\Big( \max(\text{奇数位元素}), \max(\text{偶数位元素}) \Big) $$

求最小代价。

---

二、核心思想（Key Idea）

1. 二分答案

我们要找最小的 $x$，使得： 存在一个长度 $\ge k$ 的子序列，满足：奇数位全部 $\le x$，或者偶数位全部 $\le x$。

• 若满足 → $x$ 是可行解，尝试更小的值
• 若不满足 → 需要更大的值

2. 贪心构造验证

对给定的 $x$，只需检查两种情况：

1. 情况 0：子序列奇数位所有元素 $\le x$
2. 情况 1：子序列偶数位所有元素 $\le x$ 只要任意一种情况能构造出长度 $\ge k$ 的子序列，$x$ 就合法。

---

三、贪心构造规则（最关键）

情况 0：要求奇数位 $\le x$

遍历数组，按如下规则选元素：

• 当前子序列长度为偶数（下一个要放奇数位）：必须选 $\le x$ 的元素
• 当前子序列长度为奇数（下一个要放偶数位）：随便选，无限制

情况 1：要求偶数位 $\le x$

遍历数组，按如下规则选元素：

• 当前子序列长度为奇数（下一个要放偶数位）：必须选 $\le x$ 的元素
• 当前子序列长度为偶数（下一个要放奇数位）：随便选，无限制

---

四、标程代码逐行详解

#include <bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long  // 数据范围 1e9，用 long long 保险

const int N = 2e5 + 5;

int n, k;
int a[N];

// 检查 x 是否可行
// cur=0：要求子序列 奇数位 <=x
// cur=1：要求子序列 偶数位 <=x
bool check(int x, int cur)
{
	int len = 0;  // 构造出的子序列长度
	for(int i=1; i<=n; i++)
	{
		if(!cur)  // cur=0：当前要放 偶数位，无限制，直接选
		{
			len++;
			cur ^= 1;  // 切换状态
		}
		else  // cur=1：当前要放 奇数位，必须 <=x
		{
			if(a[i] <= x)
			{
				len++;
				cur ^= 1;
			}
		}
	}
	return len >= k;  // 能构造出长度 >=k 则合法
}

// 二分答案
int binsearch(int lo, int hi)
{
	while(lo < hi)
	{
		int mid = (lo + hi) / 2;
		// 检查两种情况：奇数位限制 / 偶数位限制
		if(check(mid, 0) || check(mid, 1))
			hi = mid;  // 可行，缩小上界
		else
			lo = mid + 1;  // 不可行，增大下界
	}
	return lo;
}

int32_t main()
{
	IOS;
	cin >> n >> k;
	for(int i=1; i<=n; i++)
		cin >> a[i];
	// 二分范围：[1, 1e9]
	int ans = binsearch(1, 1e9);
	cout << ans;
	return 0;
}

---

五、函数与变量解释

1. check(x, cur) 函数

• 功能：判断 $x$ 是否能构造出满足条件的子序列
• 参数
  • $x$：当前验证的答案
  • $cur$：状态标记
    • $cur=0$ → 下一个元素放在偶数位
    • $cur=1$ → 下一个元素放在奇数位
• 返回值：构造长度 $\ge k$ 返回 true，否则 false

2. binsearch(lo, hi) 函数

• 标准二分答案模板
• 初始范围：$lo=1,\ hi=10^9$（元素值域）
• 最终 $lo=hi$，即为最小合法答案

---

六、算法复杂度分析

• 二分次数：$O(\log_2 10^9) \approx 30$
• 每次 check：$O(n)$
• 总复杂度：$O(n \cdot \log A_i) \approx 2 \times 10^5 \times 30 = 6 \times 10^6$ ✅ 完全通过时间限制

---

七、样例验证（第一个样例）

输入： $n=4,\ k=2$ 数组：$[1,2,3,4]$

二分验证 $x=1$：

• check(1,0)：构造子序列 $[1,2]$，长度 $2 \ge 2$ → 合法 答案直接为 $1$，与样例输出一致。

---

八、总结

1. 题型：最小化最大值 → 二分答案
2. 验证方法：贪心构造子序列
3. 两种检查：
   • 限制奇数位 $\le x$
   • 限制偶数位 $\le x$
4. 复杂度：$O(n \log A_i)$，最优解法
5. 代码特点：简洁高效，标准竞赛写法