题目链接：https://codeforces.com/contest/1370/problem/D
题意：长度为n的序列a中选出长度为k的子序列s，求min(max(s1,s3,s5...),max(s2,s4,s6...))
考虑二分答案，看对于二分的m，能不能构造出长度至少为k的子序列。注意题目中的式子，只要s中奇数位的值全部<=m，或者偶数位的值全部<=m即可。因此可以对奇数位和偶数位分别验证，验证的时候注意跳跃取数即可（比如验证的是奇数位，跳跃取数可以保证偶数位可以插入）。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int t,n,i,j,k,l,r,m,n1;
int a[maxn];
bool check(int x){
int len;
i=1;len=0;
if (k%2==0) n1=n-1;else n1=n;
while (i<=n1){
if (a[i]<=x){len++;i+=2; }
else i++;
}
if (k%2==0&&len>=k/2) return true;
if (k%2==1&&len>=k/2+1) return true;
i=2;len=0;
if (k%2==0) n1=n;else n1=n-1;
while (i<=n1){
if (a[i]<=x){len++;i+=2; }
else i++;
}
if (len>=k/2) return true;
return false;
}
int main(){
scanf("%d%d",&n,&k);
for (i=1;i<=n;i++) scanf("%d",&a[i]);
l=0;r=1e9;
while (r-l>1){
m=(l+r)/2;
if (check(m)) r=m;else l=m;
}
printf("%d\n",r);
return 0;
}
原文：https://www.cnblogs.com/edmunds/p/13398381.html