D. Odd-Even Subsequence

题意

给一个数组，提取一个序列，让其min(奇数位的最大值，偶数位的最大值)最小

解法

二分答案mid，然后看是否可以提取这样一个序列
一个序列的min(奇数位的最大值，偶数位的最大值) <= mid
肯定是要么奇数位的最大值 <=mid,要么是偶数位的最大值<=mid

那么就看奇数只能放<=mid的数，偶数位随便放
或者是
偶数只能放<=mid的数，奇数位随便放
看能不能提取这样两种情况之一的序列

#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
const int maxM = 1e6+10;
const int inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}
template <typename ... T>
void DummyWrapper(T... t){}

template <class T>
T unpacker(const T& t){
    cout<<' '<<t;
    return t;
}
template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout << t;
    DummyWrapper(unpacker(data)...);
    cout << '\n';
}


//--------------------------------------------
int N,K;
int a[maxn];
bool judge1(int mid){
    int sz1 = (K+1)/2,sz2 = K/2;
    int tag = 0;
    for(int i = 1;i<=N;){
        if(sz1 == 0 && sz2 == 0) break;
        if(tag == 0 && sz1) {
            tag = 1;
            i++;
            sz1--;
        }else if(tag == 1 && sz2){
            tag = 0;
            while(a[i] > mid) i++;
            if(i > N) return 0;
            i++;
            sz2--;
        }
    }
    if(sz1 == 0 && sz2 == 0) return 1;
    return 0;
}
bool judge2(int mid){
    int sz1 = (K+1)/2,sz2 = K/2;
    int tag = 0;
    for(int i = 1;i<=N;){
        if(sz1 == 0 && sz2 == 0) break;
        if(tag == 0 && sz1){
            tag = 1;
            while(a[i] > mid && i<=N) i++;
            if(i>N) return 0;
            i++;
            sz1--;

        }else if(tag == 1 && sz2){
            tag = 0;
            i++;
            sz2--;
        }
    }
    if(sz1 == 0 && sz2 == 0) return 1;
    return 0;
}
int main(){
    // debug_in;

    read(N,K);
    for(int i = 1;i<=N;i++) read(a[i]);
    int l = 1,r = 1e9,ans;
    while(l<=r){
        int mid = (l+r)>>1;
        if(judge1(mid) || judge2(mid)) r = mid-1,ans = mid;
        else l = mid+1;
    }
    printf("%d\n",ans);

    return 0;
}