Codeforces Round #651 (Div. 2) D - Odd-Even Subsequence

D - Odd-Even Subsequence

题解：因为我们要删除这个序列中的某些数，让他变成我们想要的序列，我们知道，要取得最小值，我们只需要考虑：
在构造的序列中
1.奇数序列有最小值，此时的序列偶数序列无论有多大，都不会影响答案。
2.偶数序列有最小值，此时的序列奇数序列无论有多大，都不会影响答案。
这就是我们进行check的方法
这样的话我们就可以进行二分答案了，猜测这个最小值是多少。
二分的时候，第一次跑一边奇数序列的情况，第二次跑一边偶数序列的情况，只要有一个序列的情况符合，那么答案就在左区间，如果都不符合，那么答案就在右区间

/*Keep on going Never give up*/
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
const int maxn = 2e5+10;
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
typedef long long ll;
const int mod = 1000007;
using namespace std;
int n,k;
int a[maxn];
bool che(int x){
    int cnt=0,flag=0;
    for(int i=1;i<=n;i++){
        if(flag||a[i]<=x){
            cnt++;
            flag=!flag;
        }
    }
    if(cnt>=k) return true;
    flag=1,cnt=0;
    for(int i=1;i<=n;i++){
        if(flag||a[i]<=x){
            cnt++;
            flag=!flag;
        }
    }
    if(cnt>=k) return true;
    return false;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int l=1,r=1e9;
    int mid,ans;
    while(l<=r){
        mid=(l+r)/2;
        if(che(mid)){
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}