CodeForces - 1370D Odd-Even Subsequence 二分

题意：从数组中选出一个长度为$k$的子序列，组成一个新的数组$a$,要求该数组$a$的$min(max\{a_1,a_3,a_5\},max\{a_2,a_4,a_6\})$最小

思路：假设这个答案为$x$,则$x$只能取原数组中的某个数，答案最多为$n$种，且这$n$个答案具有大小关系，可以按照从小到大排序，且值越大，其限制条件越少，越容易出现。现在要求最小值，因为满足单调性，可以采取check()二分

CHECK原理：

控制第一个最大值最小：设置一个初始值为0的索引，奇偶索引对应的其实就是得到数组中的位置的奇偶。当索引为奇数时，就判断当前数是否小于等于mid，如果否，就一直往下找；如果是，就将索引加1，表示将该数填入数组，此时该索引为偶数，索引加1，表示该数也填入数组。 相邻的这个数如果也小于等于mid是不是就浪费了？不算浪费。因为如果两个小于等于mid的数相邻，则取前者更优，可以为后面提供更多“机会”控制第二个最大值最小：同理，只需将奇偶调换即可。

代码：

const int maxn=2e6+7; const int INF=1e9; const ll INFF=1e18; int n,k,a[maxn]; bool check(int x) { int cnt=0; rep(i,1,n) { if (cnt%2) { if (a[i]<=x)cnt++; } else cnt++; } if (cnt>=k)return true; cnt=0; rep(i,1,n) { if (cnt%2==0) { if (a[i]<=x)cnt++; } else cnt++; } if (cnt>=k)return true; return false; } int main() { scanf("%d%d",&n,&k); rep(i,1,n)scanf("%d",&a[i]); int l=1,r=INF; while(l<r) { int mid=(l+r)>>1; if (check(mid))r=mid; else l=mid+1; } W(l); return 0; }